pith. sign in

arxiv: 2605.25613 · v2 · pith:JWGROJJ6new · submitted 2026-05-25 · 🧮 math.NA · cs.NA

A Jacobi-Type Eigensolver for Diagonally Dominant Symmetric Matrices

Luca Gemignani This is my paper

Pith reviewed 2026-06-29 20:38 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords Jacobi iterationeigenpair computationdiagonally dominant matricessymmetric matriceslinear convergencequadratic complexitynumerical linear algebra
0
0 comments X

The pith

A Jacobi-type iteration computes a specified eigenpair of significantly diagonally dominant symmetric matrices in quadratic time.

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

The paper introduces a Jacobi-type iterative procedure for finding one specified eigenpair of a symmetric matrix. It proves that the iteration converges linearly when the matrix is significantly diagonally dominant, with the rate controlled by the strength of that dominance. Each iteration performs a quadratic amount of work. This combination yields an overall quadratic-time algorithm for approximating the eigenpair. A reader would care because many practical symmetric matrices from applications satisfy the dominance condition and need only one eigenpair rather than a full decomposition.

Core claim

The procedure is a Jacobi-type iteration for a given specified eigenpair of a symmetric matrix. For a certain class of diagonally dominant matrices, the procedure is shown to converge at a linear rate depending on how the matrix is significantly dominated. The cost per iteration is generally quadratic. Therefore, the proposed procedure can compute an approximation of the desired eigenpair in quadratic time.

What carries the argument

The Jacobi-type iteration that updates matrix entries to isolate the target eigenpair while maintaining symmetry.

If this is right

  • Linear convergence holds precisely when the matrix satisfies the significant diagonal dominance condition.
  • The convergence speed is governed by a quantity measuring the degree of dominance.
  • Work per iteration scales quadratically with matrix dimension.
  • An approximate eigenpair is obtained after a quadratic number of total operations.

Where Pith is reading between the lines

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

  • The explicit dependence of the rate on dominance allows a priori estimates of the number of iterations needed.
  • The method targets problems where only one eigenpair is required rather than the full spectrum.
  • Quadratic overall cost makes the approach attractive for moderately large matrices arising in applications that produce diagonally dominant structure.

Load-bearing premise

The input symmetric matrix must belong to the class of significantly diagonally dominant matrices.

What would settle it

Apply the iteration to a symmetric matrix that is diagonally dominant but falls below the significance threshold and check whether the error reduction follows the claimed linear rate or fails to converge linearly.

Figures

Figures reproduced from arXiv: 2605.25613 by Luca Gemignani.

Figure 1
Figure 1. Figure 1: Convergence history of the quantities computed by our modification of the Jacobi [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Convergence history for Procedure EIG DDSM. The figure on the left shows the convergence of off(A (k) (m, : )) whereas the figure on the right hand side gives the monotonic decreasing of off(A (k) ). the convergence of the iterative algorithm can be excruciatingly slow. More￾over, the result stated in Theorem 3 does not generally guarantee that a (k) m,m is an approximation of the sought m−th eigenvalue of… view at source ↗
Figure 3
Figure 3. Figure 3: Reduction of off(H (10(ℓ−1)(6, : )) in the first steps of Algorithm 1 applied to the matrix A of Example 5 with m = 6. For the leukemia dataset we find γ2 = 3.45×10−3 and α0 ≃ 1 and, therefore, the condition α0 ≤ C min{ 1 n , γ} is not fulfilled for any constant C < 1. In order to understand the results in [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Convergence history of Algorithm 1 applied for the approximation of the second and the third eigenvalue of the normalized Laplacian generated from the wine-quality dataset. 0 5 10 15 20 25 30 35 40 10 -12 10 -10 10 -8 10 -6 10 -4 10 -2 10 0 0 5 10 15 20 25 30 35 40 10 -5 10 -4 10 -3 10 -2 10 -1 10 0 10 1 [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Convergence history of Algorithm 1 applied for the approximation of the second eigenvalue of the normalized Laplacian generated from G22. The plots on the left and on the right show the convergence of errj and off(L ((n−1)(j−1))(2, : )), respectively. are associated with a progressive deterioration of the convergence. Sim￾ilar behaviors are also observed with adjacency matrices generated from random undire… view at source ↗
Figure 6
Figure 6. Figure 6: Sparsity patterns of the adjacency matrix generated from G22 and its permuted [PITH_FULL_IMAGE:figures/full_fig_p014_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Convergence history of Algorithm 1 applied for the approximation of the smallest eigenvalue of matrices generated from Problem 422. The plot on the left show the errors for the normalized Laplacian. The plot on the right gives the errors for the modified matrix. lustrate the convergence of our proposed method for the approximation of the smallest eigenvalue of the normalized Laplacian generated from A and … view at source ↗
Figure 8
Figure 8. Figure 8: Convergence history of Algorithm 1 applied to the matrix (7). The plots on the left and on the right shows the convergence of errj and off(A ((n−1)(j−1))(m, : )), respectively. is worth noting the different behaviors. For m = 1 we find α0 ≃ 0.3 and γ1 = 4.8 × 10−4 . The initial error is quite small and the algorithm proceeds very quickly with the refinement. For m = n + 1 2 , γm ≃ γ1 but the initial error … view at source ↗
Figure 9
Figure 9. Figure 9: Plot of eigenvalue paths and of the step length function for a random matrix [PITH_FULL_IMAGE:figures/full_fig_p016_9.png] view at source ↗
read the original abstract

This paper presents a Jacobi-type iteration for computing a given specified eigenpair of a symmetric matrix. For a certain class of diagonally dominant matrices, the procedure is shown to converge at a linear rate depending on how the matrix is significantly dominated. The cost per iteration is generally quadratic. Therefore, the proposed procedure can compute an approximation of the desired eigenpair in quadratic time.

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

1 major / 0 minor

Summary. The paper presents a Jacobi-type iteration for computing a specified eigenpair of a symmetric matrix. For a certain class of diagonally dominant matrices, the procedure is shown to converge at a linear rate depending on how the matrix is significantly dominated. The cost per iteration is generally quadratic. Therefore, the proposed procedure can compute an approximation of the desired eigenpair in quadratic time.

Significance. If the convergence result holds for the stated matrix class and the complexity analysis is corrected, the method could offer a specialized, efficient approach for eigenpair computation in applications involving strongly diagonally dominant symmetric matrices. The linear convergence rate tied to the dominance parameter is a potentially useful feature, but the overall runtime claim requires adjustment to reflect standard iteration counts.

major comments (1)
  1. [Abstract] Abstract: The claim that the eigenpair can be computed 'in quadratic time' is not supported by the described linear convergence. Linear convergence reduces the error by a fixed factor ρ < 1 per iteration (with ρ depending on dominance), requiring Θ(log(1/ε)) iterations to reach accuracy ε. Combined with O(n²) work per iteration, the total cost is O(n² log(1/ε)), not quadratic, unless the number of iterations is bounded independently of ε (which is not stated).

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and for identifying the inconsistency between the stated linear convergence and the runtime claim in the abstract. We agree that the complexity statement requires correction and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract: The claim that the eigenpair can be computed 'in quadratic time' is not supported by the described linear convergence. Linear convergence reduces the error by a fixed factor ρ < 1 per iteration (with ρ depending on dominance), requiring Θ(log(1/ε)) iterations to reach accuracy ε. Combined with O(n²) work per iteration, the total cost is O(n² log(1/ε)), not quadratic, unless the number of iterations is bounded independently of ε (which is not stated).

    Authors: We agree with the referee's observation. The abstract's claim of quadratic time is incorrect because the convergence is linear with rate depending on the dominance parameter, leading to a total complexity of O(n² log(1/ε)). We will revise the abstract (and any similar statements in the introduction or conclusion) to accurately report the complexity as O(n² log(1/ε)). This change does not affect the convergence theorem or the per-iteration cost analysis, which remain the core contributions. revision: yes

Circularity Check

0 steps flagged

No circularity: convergence rate and complexity derived from explicit proof and cost analysis

full rationale

The paper states that linear convergence is shown (proven) for a defined class of significantly diagonally dominant symmetric matrices, with per-iteration cost generally quadratic, yielding the quadratic-time claim. No equations reduce a claimed result to a fitted parameter, self-definition, or self-citation chain; the derivation chain is self-contained via standard analysis of the iteration without importing load-bearing uniqueness or ansatzes from prior author work. The skeptic's log-factor observation concerns completeness of the complexity statement rather than any definitional circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are identifiable from the abstract alone.

pith-pipeline@v0.9.1-grok · 5571 in / 954 out tokens · 29140 ms · 2026-06-29T20:38:10.078754+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

19 extracted references

  1. [1]

    Altafini

    C. Altafini. Stability analysis of diagonally equipotent matrices.Automat- ica, 49(9):2780–2785, 2013

    2013

  2. [2]

    Barlow and J

    J. Barlow and J. Demmel. Computing accurate eigensystems of scaled diagonally dominant matrices.SIAM Journal on Numerical Analysis, 27(3):762–791, 1990

    1990

  3. [3]

    R. P. Brent and F. T. Luk. The solution of singular-value and symmet- ric eigenvalue problems on multiprocessor arrays.SIAM J. Scientific and Statistical Computing, 6:69–84, 1985

    1985

  4. [4]

    Bunch and C.P

    J.R. Bunch and C.P. Nielsen. Updating the singular value decomposition. Numerische Mathematik, 31(2):111–129, 1978/79

    1978

  5. [5]

    Drmaˇ c and K

    Z. Drmaˇ c and K. Veseli´ c. Approximate eigenvectors as preconditioner. Linear Algebra and its Applications, 309(1):191–215, 2000

    2000

  6. [6]

    Eidelman, L

    Y. Eidelman, L. Gemignani, and I. Gohberg. Efficient eigenvalue computa- tion for quasiseparable Hermitian matrices under low rank perturbations. Numerical Algorithms, 47:253–273, 2008

    2008

  7. [7]

    G. H. Golub and H. A. van der Vorst. Eigenvalue computation in the 20th century.Journal of Computational and Applied Mathematics, 123(1):35–65,

  8. [8]

    Numerical Analysis 2000. Vol. III: Linear Algebra. 16

    2000

  9. [9]

    G.H. Golub. Some modified matrix eigenvalue problems.SIAM Review, 15:318–334, 1973

    1973

  10. [10]

    Golub, D.K

    T.R. Golub, D.K. Slonim, P. Tamayo, C. Huard, M. Gaasenbeek, J.P. Mesirov, H. Coller, M.L. Loh, J.R. Downing, M.A. Caligiuri, C.D. Bloom- field, and E.S. Lander. Molecular classification of cancer: class dis- covery and class prediction by gene expression monitoring.Science, 286(5439):531–537, October 1999

    1999

  11. [11]

    Hari and Z

    V. Hari and Z. Drmac. On scaled almost-diagonal Hermitian matrix pairs. SIAM Journal on Matrix Analysis and Applications, 18(4):1000–1012, 1997

    1997

  12. [12]

    Higham, G

    D.J. Higham, G. Kalna, and M. Kibble. Spectral clustering and its use in bioinformatics.Journal of Computational and Applied Mathematics, 204(1):25–37, 2007. Special issue dedicated to Professor Shinnosuke Oharu on the occasion of his 65th birthday

    2007

  13. [13]

    Limebeer

    D.J.N. Limebeer. The application of generalized diagonal dominance to linear system stability theory.International Journal of Control, 36(2):185– 212, 1982

    1982

  14. [14]

    Matejaˇ s

    J. Matejaˇ s. Quadratic convergence of scaled matrices in Jacobi method. Numerische Mathematik, 87(1):171–199, Nov 2000

    2000

  15. [15]

    Matejaˇ s

    J. Matejaˇ s. Quadratic convergence bounds of scaled iterates by the serial Jacobi method for indefinite Hermitian matrices.Electronic Journal of Linear Algebra, 17:62–87, 2008

    2008

  16. [16]

    A. Melman. A numerical comparison of methods for solving secular equa- tions.J. Comput. Appl. Math., 86(1):237–249, 1997. Special issue dedicated to William B. Gragg (Monterey, CA, 1996)

    1997

  17. [17]

    A. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In T. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems, volume 14. MIT Press, 2001

    2001

  18. [18]

    N. Sebe. Diagonal dominance and integrity. InProceedings of 35th IEEE Conference on Decision and Control, volume 2, pages 1904–1909 vol.2, 1996

    1904

  19. [19]

    P. Tilli. Polynomial root finding by means of continuation.Computing, 59(4):307–324, 1997. 17

    1997