pith. sign in

arxiv: 2411.02895 · v2 · pith:E5PWJ2VLnew · submitted 2024-11-05 · 🧮 math.NA · cs.NA

The shift-and-invert Arnoldi method for singular matrix pencils

Karl Meerbergen , Zhijun Wang This is my paper

Pith reviewed 2026-05-23 17:57 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords singular matrix pencilsshift-and-invert Arnoldisparse LU factorizationregularizationeigenvalue problemsnumerical linear algebrarank detection
0
0 comments X

The pith

Sparse regularization from LU pivoting enables shift-and-invert Arnoldi iteration on singular matrix pencils.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper adapts the shift-and-invert Arnoldi method to singular matrix pencils by constructing regularization matrices from the pivoting sequence of a sparse LU factorization instead of random choices. This keeps the matrices sparse, which the authors show supports better performance and accuracy for large problems while often revealing the normal rank during factorization. A rank correction step handles cases where rank detection fails, and existing sparse solvers supply the needed pivoting for rectangular full-rank cases. A sympathetic reader cares because the method turns a standard direct factorization step into a reliable way to regularize singular eigenproblems without randomization overhead.

Core claim

The central claim is that regularization matrices taken from the pivoting sequence of a sparse LU factorization are suitable for converting singular pencils into regular ones so that the shift-and-invert Arnoldi method converges to the desired eigenvalues, and that the same factorization frequently identifies the normal rank correctly.

What carries the argument

Regularization matrix constructed directly from the pivoting sequence of sparse LU factorization applied to the singular pencil.

If this is right

  • The LU factorization often detects the normal rank of the pencil during the process.
  • A rank correction method can be applied when the detected rank is incorrect.
  • Sparsity preservation improves both performance and accuracy relative to randomized regularization.
  • Pivoting sequences from existing sparse direct solvers can be reused directly for full-rank rectangular eigenvalue problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same pivoting-derived regularization could be tested in other Krylov methods that require matrix inverses or solves on singular pencils.
  • Combining the deterministic LU approach with occasional randomized verification might increase robustness without losing the sparsity benefit.
  • The method indicates that structure extracted from direct solvers can serve as a deterministic alternative to randomness in other regularization settings.

Load-bearing premise

The pivoting sequence from sparse LU factorization produces a regularization matrix that preserves the essential spectral properties of the original singular pencil sufficiently well for the shift-and-invert Arnoldi iteration to converge to the desired eigenvalues.

What would settle it

Numerical counterexamples on singular pencils where the LU-derived regularization produces eigenvalues or convergence behavior that differ from those obtained with a verified correct regularization or exact reference solution would falsify the central claim.

read the original abstract

A popular method for solving large sparse regular eigenvalue problem is the shift-and-invert Arnoldi method. This paper aims to use the method for large sparse singular pencils. In three recent papers, {\em Hochstenbach, Mehl, and Plestenjak, 2019, 2023, and 2024}, propose regularization of the singular pencil, using randomly chosen regularization matrices. We propose sparse regularization matrices obtained from the pivoting sequence of a sparse LU factorization. As a side effect, the LU factorization often is rank revealing, which facilitates finding a regularization. Numerical examples illustrate that the LU factorization mostly detects the normal rank and finds a suitable sparse regularization. A rank correction method is proposed for the cases where the normal rank is not determined correctly. For full rank rectangular eigenvalue problems, the pivoting sequence of existing sparse direct system solvers can be used. We compare with randomized regularization methods: preservation of sparsity is beneficial for performance, and often, the accuracy of the eigenvalue solver.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The manuscript proposes adapting the shift-and-invert Arnoldi method to large sparse singular matrix pencils by constructing sparse regularization matrices from the pivoting sequence of a sparse LU factorization, as an alternative to the random regularization matrices introduced in Hochstenbach–Mehl–Plestenjak (2019, 2023, 2024). It observes that the LU factorization frequently reveals the normal rank, supplies an explicit rank-correction procedure for the remaining cases, and reports numerical comparisons showing that sparsity preservation improves both runtime and accuracy relative to randomized regularizers. For rectangular full-rank problems the pivoting information from existing sparse direct solvers is reused.

Significance. If the reported empirical behavior generalizes, the approach supplies a practical, sparsity-preserving route to regularizing singular pencils that re-uses standard sparse-direct infrastructure already present in most large-scale eigenvalue codes. This could reduce fill-in and memory traffic for problems where random regularization produces dense factors, while the rank-revealing side-effect of LU offers an inexpensive diagnostic. The contribution is primarily algorithmic and empirical rather than theoretical.

major comments (2)
  1. [Numerical examples] Numerical examples section: the central claim that LU-derived regularization “preserves the essential spectral properties” sufficiently for Arnoldi convergence rests entirely on the reported test-suite behavior; no quantitative bound or perturbation analysis is given that would indicate when the pivoting sequence fails to produce a spectrally faithful regularizer (cf. the weakest assumption noted in the reader’s report).
  2. [Method / rank correction] Rank-correction procedure (described after the LU discussion): the manuscript states that a correction is applied when the normal rank is misidentified, but does not specify the algebraic form of the correction matrix or prove that the corrected pencil remains regular with the same finite eigenvalues as the original; this step is load-bearing for the method’s reliability on the failure cases.
minor comments (3)
  1. [Introduction] The abstract and introduction cite the three Hochstenbach–Mehl–Plestenjak papers but do not clarify which specific regularization construction from those works is being compared; a short table or sentence mapping the randomized constructions would improve readability.
  2. [Numerical examples] Figure captions and table headings should explicitly state the matrix dimensions, normal rank, and shift value used for each example so that the sparsity and accuracy claims can be reproduced without consulting the text.
  3. [Method] Notation for the regularized pencil (A + UV^T, B + UV^T or similar) is introduced informally; a single displayed equation defining the regularized pair would eliminate ambiguity when the same symbols appear in the Arnoldi iteration.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive report and positive recommendation. We address the two major comments point by point below, indicating planned revisions where appropriate.

read point-by-point responses

  1. Referee: Numerical examples section: the central claim that LU-derived regularization “preserves the essential spectral properties” sufficiently for Arnoldi convergence rests entirely on the reported test-suite behavior; no quantitative bound or perturbation analysis is given that would indicate when the pivoting sequence fails to produce a spectrally faithful regularizer (cf. the weakest assumption noted in the reader’s report).

    Authors: We agree that the manuscript is primarily algorithmic and empirical, with no new perturbation theory or quantitative bounds provided for the LU-based regularizer. The approach is motivated by the practical observation that sparse LU pivoting frequently yields a spectrally suitable regularizer (often revealing normal rank), and the numerical comparisons demonstrate advantages in sparsity, runtime, and accuracy over random regularization. Like the randomized methods in Hochstenbach–Mehl–Plestenjak (2019, 2023, 2024), the method relies on empirical validation rather than a priori guarantees. In revision we will add an explicit statement in the numerical examples and conclusions sections acknowledging the absence of theoretical bounds and the reliance on test-suite evidence. revision: partial

  2. Referee: Rank-correction procedure (described after the LU discussion): the manuscript states that a correction is applied when the normal rank is misidentified, but does not specify the algebraic form of the correction matrix or prove that the corrected pencil remains regular with the same finite eigenvalues as the original; this step is load-bearing for the method’s reliability on the failure cases.

    Authors: The rank-correction procedure is outlined in Section 3.2, where the correction matrix is formed by augmenting the regularization using the detected rank deficiency from the LU factors to restore regularity while preserving the finite spectrum. We acknowledge that the current description is concise and does not include an expanded algebraic definition or a self-contained proof of eigenvalue invariance. In the revised manuscript we will supply the explicit construction of the correction matrix (a low-rank update derived from the null-space information) together with a short argument showing that the finite eigenvalues remain unchanged because the correction acts only on the infinite-eigenvalue structure. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper introduces a sparse regularization for singular pencils derived from the pivoting sequence of a standard sparse LU factorization, then validates it empirically via numerical examples against randomized regularizers from unrelated prior work (Hochstenbach et al.). No load-bearing step reduces a claimed result to a fitted parameter, self-definition, or self-citation chain; the method and its rank-correction fallback are presented as direct applications of existing sparse direct solvers, with performance and accuracy gains treated as observable outcomes rather than tautological consequences of the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The method rests on standard properties of sparse LU factorization and the shift-and-invert Arnoldi iteration; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Sparse LU factorization with partial pivoting produces a sequence that can be used to construct a regularization matrix preserving the normal rank and spectral properties of the pencil.
    Invoked in the description of the proposed regularization and numerical examples.

pith-pipeline@v0.9.0 · 5697 in / 1333 out tokens · 22060 ms · 2026-05-23T17:57:32.066714+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Solving linear-rate ODE hierarchies (like master equations) using closures and operator splitting

    math.NA 2026-05 unverdicted novelty 7.0

    For linear-rate master equations the generating function admits an exact composition-multiplier representation whose Taylor coefficients on any finite window are obtained from a closed lower-triangular ODE of size 2(N...

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages · cited by 1 Pith paper

  1. [1]

    F. V. Atkinson and A. Mingarelli , Multiparameter eigenvalue problems , vol. 1, Academic Press New York, 1972

    work page 1972

  2. [2]

    Byers, V

    R. Byers, V. Mehrmann, and H. Xu , A structured staircase algorithm for skew- symmetric/symmetric pencils, Electronic Transactions on Numerical Analysis, 26 (2007), pp. 1–33. SHIFT-AND-INVERT FOR SINGULAR PENCIL 19

    work page 2007

  3. [3]

    Claes, E

    R. Claes, E. Jarlebring, K. Meerbergen, and P. Upadhyaya , Linearizable eigenvector nonlinearities, SIAM Journal on Matrix Analysis and Applications, 43 (2022), pp. 764– 786, https://doi.org/10.1137/21m142931x

    work page doi:10.1137/21m142931x 2022

  4. [4]

    COTTIN, Dynamic model updating—a multiparameter eigenvalue problem, Mechanical Sys- tems and Signal Processing, 15 (2001), pp

    N. COTTIN, Dynamic model updating—a multiparameter eigenvalue problem, Mechanical Sys- tems and Signal Processing, 15 (2001), pp. 649–665, https://doi.org/10.1006/mssp.2000. 1362

    work page doi:10.1006/mssp.2000 2001

  5. [5]

    B. Dong, B. Yu, and Y. Yu , A homotopy method for finding all solutions of a multiparam- eter eigenvalue problem , SIAM Journal on Matrix Analysis and Applications, 37 (2016), pp. 550–571, https://doi.org/10.1137/140958396

    work page doi:10.1137/140958396 2016

  6. [6]

    Gantmacher, The theory of matrices , Chelsea Publishing Company, (1959)

    F. Gantmacher, The theory of matrices , Chelsea Publishing Company, (1959)

    work page 1959

  7. [7]

    M. E. Hochstenbach, T. Ko ˇsir, and B. Plestenjak , Numerical methods for rectangular multiparameter eigenvalue problems, with applications to finding optimal arma and lti models, Numerical Linear Algebra with Applications, (2023), https://doi.org/10.1002/nla. 2540

    work page doi:10.1002/nla 2023

  8. [8]

    M. E. Hochstenbach, C. Mehl, and B. Plestenjak , Solving singular generalized eigen- value problems by a rank-completing perturbation , SIAM Journal on Matrix Analysis and Applications, 40 (2019), pp. 1022–1046, https://doi.org/10.1137/18m1188628

    work page doi:10.1137/18m1188628 2019

  9. [9]

    M. E. Hochstenbach, C. Mehl, and B. Plestenjak , Solving singular generalized eigenvalue problems. part ii: Projection and augmentation , SIAM Journal on Matrix Analysis and Applications, 44 (2023), pp. 1589–1618, https://doi.org/10.1137/22m1513174

    work page doi:10.1137/22m1513174 2023

  10. [10]

    M. E. Hochstenbach, A. Muhi ˇc, and B. Plestenjak , Jacobi–davidson methods for polyno- mial two-parameter eigenvalue problems , Journal of Computational and Applied Mathe- matics, 288 (2015), pp. 251–263, https://doi.org/10.1016/j.cam.2015.04.019

    work page doi:10.1016/j.cam.2015.04.019 2015

  11. [11]

    Li and T

    T. Li and T. Sauer , Homotopy method for generalized eigenvalue problems ax= λbx, Linear Algebra and its Applications, 91 (1987), pp. 65–74

    work page 1987

  12. [12]

    Lietaert, K

    P. Lietaert, K. Meerbergen, and F. Tisseur , Compact two-sided Krylov metods for non- linear eigenvalue problems, 40 (2018), pp. A2801–A2829

    work page 2018

  13. [13]

    Meerbergen and A

    K. Meerbergen and A. Spence , Implicitly restarted arnoldi with purification for the shift- invert transformation, Mathematics of Computation, 66 (1997), pp. 667–689, https://doi. org/10.1090/s0025-5718-97-00844-2

    work page doi:10.1090/s0025-5718-97-00844-2 1997

  14. [14]

    Muhiˇc and B

    A. Muhiˇc and B. Plestenjak , A method for computing all values λ such that a+ λb has a multiple eigenvalue, Linear Algebra and its Applications, 440 (2014), pp. 345–359

    work page 2014

  15. [15]

    Shadan, F

    F. Shadan, F. Khoshnoudian, and A. Esfandiari , A frequency response-based structural damage identification using model updating method: Model updating using incomplete frfs , Structural Control and Health Monitoring, 23 (2015), pp. 286–302, https://doi.org/10. 1002/stc.1768

    work page 2015

  16. [16]

    Shapiro and M

    B. Shapiro and M. Shapiro , On eigenvalues of rectangular matrices , Proceedings of the Steklov Institute of Mathematics, 267 (2009), pp. 248–255, https://doi.org/10.1134/ s0081543809040208

    work page 2009

  17. [17]

    Z. Wang, B. Dong, Y. Yu, X. Zhao, and Y. Fang, The structured multiparameter eigenvalue problems in finite element model updating problems, Structural Engineering and Mechanics, 88 (2023), pp. 493–500

    work page 2023

  18. [18]

    Zhang, K

    T. Zhang, K. H. Law, and G. H. Golub , On the homotopy method for perturbed symmet- ric generalized eigenvalue problems , SIAM Journal on Scientific Computing, 19 (1998), pp. 1625–1645, https://doi.org/10.1137/s1064827596299755

    work page doi:10.1137/s1064827596299755 1998