pith. sign in

arxiv: 2606.04259 · v1 · pith:DIKYBY7Ynew · submitted 2026-06-02 · 🧮 math.NA · cs.NA

An indefinite LOBPCG type of algorithm for detecting a definite Hermitian matrix pair

Pith reviewed 2026-06-28 08:35 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords Hermitian matrix pairsdefiniteness detectionLOBPCGsubspace iterationnumerical linear algebraindefinite matricespreconditioned methodslarge-scale matrices
0
0 comments X

The pith

An LOBPCG-style subspace iteration detects definiteness of large Hermitian matrix pairs by testing small projected pairs.

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

The paper develops a subspace algorithm to determine whether a large Hermitian pair (A, B) with indefinite B is definite, that is, whether some real linear combination of A and B is positive definite. The approach repeatedly builds small subspaces and checks the definiteness property on the resulting low-dimensional projected pairs. A specialized version sets the subspace dimension to m=3 and constructs the subspaces exactly as in the indefinite LOBPCG method, with an optional preconditioned variant. Numerical tests on medium-sized, large, and banded pairs show that the method identifies (in)definiteness much faster than several existing algorithms.

Core claim

The central claim is that iterative testing of small projected Hermitian pairs formed from LOBPCG-style subspaces of dimension m=3 reliably detects the global definiteness property of the original large pair.

What carries the argument

The specialized algorithm with parameter m that generates three-dimensional subspaces in the style of the indefinite LOBPCG method and tests definiteness on the resulting projected pairs.

If this is right

  • The algorithm scales to large and banded pairs where dense methods become impractical.
  • Preconditioning can be added to the subspace construction to reduce the number of iterations needed for detection.
  • The same subspace-testing idea applies directly to medium-sized pairs with only modest overhead.
  • Repeated testing of projected pairs replaces the need for a single expensive global computation of all possible linear combinations.

Where Pith is reading between the lines

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

  • The technique could be combined with other iterative eigensolvers when definiteness must be checked before solving a related eigenproblem.
  • Similar low-dimensional projection tests might apply to detecting other matrix properties such as stability or hyperbolicity in nearby problem classes.
  • For matrices with additional structure such as sparsity patterns beyond banding, the subspace dimension m might be tuned adaptively rather than fixed at three.

Load-bearing premise

The LOBPCG-style subspaces of dimension three are assumed to be rich enough that any positive definite linear combination, if it exists, will appear as a positive definite combination inside one of the tested small projected pairs.

What would settle it

A definite Hermitian pair (A, B) on which the algorithm returns 'indefinite' on every run because no tested three-dimensional subspace ever captures a positive definite combination.

read the original abstract

A Hermitian matrix pair $(A,B)$ is called definite if some real linear combination of the matrices $A$ and $B$ is a positive definite matrix. Detection of the definiteness is not straightforward. We propose a basic subspace algorithm for detecting a large definite matrix pair $(A,B)$ with indefinite $B$. The proposed subspace algorithm is based on iterative testing of small projected Hermitian matrix pairs formed by using subspaces of small dimensions. Furthermore, we propose a specialized algorithm with parameter $m$, and its preconditioned variant. In the specialized algorithm with $m=3$ we choose the subspaces like in the indefinite locally optimal block preconditioned conjugate gradient (LOBPCG) method. Numerical experiments demonstrate the efficiency of our specialized algorithm, applied on medium-sized pairs, as well as, on large and banded pairs. Our algorithm very quickly detects (in)definiteness; much faster than some other algorithms.

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 / 2 minor

Summary. The manuscript proposes a basic subspace iteration algorithm and a specialized variant (with parameter m=3) based on indefinite LOBPCG subspaces for detecting whether a Hermitian pair (A,B) with indefinite B is definite, i.e., admits some real linear combination that is positive definite. The method repeatedly forms and tests small projected pairs; if any projected pair is definite then the original pair is definite. Numerical experiments on medium-sized, large, and banded pairs are presented to show that the algorithm detects (in)definiteness quickly and is faster than some existing methods.

Significance. If the detection procedure is reliable, the work supplies a practical tool for large-scale definiteness testing where dense methods are prohibitive. The adaptation of LOBPCG-style block updates to the definiteness-detection setting is a novel algorithmic idea, and the reported performance on banded pairs is a concrete strength. However, the absence of any convergence or correctness argument limits the result's theoretical impact within numerical linear algebra.

major comments (2)
  1. [§3] §3 (specialized algorithm with m=3): no argument is supplied that the LOBPCG-style iteration is guaranteed to produce, in finite steps, a subspace containing a vector x such that x^*(αA+βB)x>0 for the unknown (α,β) that renders the pair definite. This is load-bearing for the central claim of correctly detecting definiteness, because a certifying direction orthogonal to the growing subspace for many iterations would cause the algorithm to report indefiniteness on all tested projections while the pair is actually definite.
  2. [Numerical experiments] Numerical experiments section: the claim that the algorithm 'very quickly detects (in)definiteness; much faster than some other algorithms' rests on unspecified test matrices, unspecified ground-truth verification of definiteness, and unnamed comparison methods. Without these details it is impossible to evaluate whether the reported speed advantage is robust or whether false-negative cases were examined.
minor comments (2)
  1. The abstract refers to 'some other algorithms' without naming them; the introduction should explicitly list the competing methods used in the timing comparisons.
  2. Notation for the linear combination coefficients (α,β) is introduced only informally; a short paragraph defining the definiteness test on the projected pair would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and indicate the revisions planned.

read point-by-point responses
  1. Referee: [§3] §3 (specialized algorithm with m=3): no argument is supplied that the LOBPCG-style iteration is guaranteed to produce, in finite steps, a subspace containing a vector x such that x^*(αA+βB)x>0 for the unknown (α,β) that renders the pair definite. This is load-bearing for the central claim of correctly detecting definiteness, because a certifying direction orthogonal to the growing subspace for many iterations would cause the algorithm to report indefiniteness on all tested projections while the pair is actually definite.

    Authors: We acknowledge that no convergence or correctness argument is supplied for the specialized m=3 variant. The algorithm is presented as a practical heuristic extending the LOBPCG framework, with effectiveness demonstrated through numerical experiments rather than theoretical guarantees. We agree that the possibility of a certifying direction remaining orthogonal to the subspace constitutes a genuine limitation. In the revised manuscript we will add an explicit discussion in Section 3 stating the heuristic character of the method, describing this potential failure mode, and recommending multiple random initializations as a practical safeguard. revision: yes

  2. Referee: [Numerical experiments] Numerical experiments section: the claim that the algorithm 'very quickly detects (in)definiteness; much faster than some other algorithms' rests on unspecified test matrices, unspecified ground-truth verification of definiteness, and unnamed comparison methods. Without these details it is impossible to evaluate whether the reported speed advantage is robust or whether false-negative cases were examined.

    Authors: We accept that the experimental section requires greater explicitness for reproducibility and evaluation. The revised version will expand the numerical experiments section to detail the precise matrix constructions (dimensions, generation procedures, and banded structures), the methods used to establish ground-truth definiteness (dense verification on medium cases and structural properties on constructed examples), the specific comparison algorithms with references, and additional test cases targeting potential false negatives to assess robustness. revision: yes

Circularity Check

0 steps flagged

No circularity: algorithm is a constructive procedure validated by external experiments

full rationale

The paper presents a subspace iteration algorithm (with m=3 LOBPCG-style subspaces) that repeatedly forms and tests small projected pairs to detect definiteness of (A,B). This is a direct computational procedure whose termination condition is the sign of the smallest eigenvalue of the projected pair; it does not define any quantity in terms of itself, rename a fitted parameter as a prediction, or rest its correctness on a self-citation chain. The cited LOBPCG method is an external standard reference, and the numerical results on medium, large, and banded pairs constitute independent empirical checks rather than tautological reductions. No load-bearing step equates the claimed detection outcome to an input by construction.

Axiom & Free-Parameter Ledger

1 free parameters · 0 axioms · 0 invented entities

The central claim rests on the unstated premise that definiteness of the full pair is detectable from definiteness of its projections onto low-dimensional subspaces chosen via LOBPCG rules; no free parameters beyond the block size m are named, and no new entities are introduced.

free parameters (1)
  • m
    Block size parameter in the specialized algorithm; set to 3 in the described variant.

pith-pipeline@v0.9.1-grok · 5687 in / 1180 out tokens · 19071 ms · 2026-06-28T08:35:41.240932+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

50 extracted references · 36 canonical work pages

  1. [1]

    Eigenvalue-basedalgorithmandanal- ysis for nonconvex QCQP with one constraint

    Adachi, S., Nakatsukasa, Y., 2019. Eigenvalue-basedalgorithmandanal- ysis for nonconvex QCQP with one constraint. Math. Program. 173, 33 79–116. doi:10.1007/s10107-017-1206-8

  2. [2]

    Convergence analysis of vector extended lo- cally optimal block preconditioned extended conjugate gradient method for computing extreme eigenvalues

    Benner, P., Liang, X., 2022. Convergence analysis of vector extended lo- cally optimal block preconditioned extended conjugate gradient method for computing extreme eigenvalues. Numer. Linear Algebra Appl. 29. doi:10.1002/nla.2445

  3. [3]

    Betcke, T., Higham, N.J., Mehrmann, V., Schröder, C., Tisseur, F.,

  4. [4]

    ACM Trans

    NLEVP: A collection of nonlinear eigenvalue problems. ACM Trans. Math. Software 39, 1–28. doi:10.1145/2427023.2427024

  5. [5]

    Some stable methods for calculating inertia and solving symmetric linear systems

    Bunch, J.R., Kaufman, L., 1977. Some stable methods for calculating inertia and solving symmetric linear systems. Math. Comp. 31, 163–179. doi:10.2307/2005787

  6. [6]

    A simplified pivoting strategy for symmetric tridiagonal matrices

    Bunch, J.R., Marcia, R.F., 2006. A simplified pivoting strategy for symmetric tridiagonal matrices. Numer. Linear Algebra Appl. 13, 865–

  7. [7]

    Direct methods for solving symmetric indefinite systems of linear equations

    Bunch, J.R., Parlett, B.N., 1971. Direct methods for solving symmetric indefinite systems of linear equations. SIAM J. Numer. Anal. 8, 639–655. doi:10.1137/0708060

  8. [8]

    The nearest definite pair for the Hermitian generalized eigenvalue problem

    Cheng, S.H., Higham, N.J., 1999. The nearest definite pair for the Hermitian generalized eigenvalue problem. Linear Algebra Appl. 302– 303, 63–76. doi:10.1016/S0024-3795(99)00026-9

  9. [9]

    Algorithm 646: PDFIND: A routine to find a pos- itive definite linear combination of two real symmetric matrices

    Crawford, C.R., 1986. Algorithm 646: PDFIND: A routine to find a pos- itive definite linear combination of two real symmetric matrices. ACM Trans. Math. Software 12, 278–282. doi:10.1145/7921.214335

  10. [10]

    Finding a positive definite linear combination of two Hermitian matrices

    Crawford, C.R., Moon, Y.S., 1983. Finding a positive definite linear combination of two Hermitian matrices. Linear Algebra Appl. 51, 37–

  11. [11]

    doi:10.1016/0024-3795(83)90148-9

  12. [12]

    Analysis of the Cholesky method with iterative refinement for solving the symmetric definite generalized eigenproblem

    Davies, P.I., Higham, N.J., Tisseur, F., 2001. Analysis of the Cholesky method with iterative refinement for solving the symmetric definite generalized eigenproblem. SIAM J. Matrix Anal. Appl. 23, 472–493. doi:10.1137/S0895479800373498. 34

  13. [13]

    On quadratic convergence bounds for the J-symmetric Jacobi method

    Drmač, Z., Hari, V., 1993. On quadratic convergence bounds for the J-symmetric Jacobi method. Numer. Math. 64, 147–180. doi:10.1007/ BF01388685

  14. [14]

    Algorithm 866: IFISS, a Matlab toolbox for modelling incompressible flow

    Elman, H.C., Ramage, A., Silvester, D.J., 2007. Algorithm 866: IFISS, a Matlab toolbox for modelling incompressible flow. ACM Trans. Math. Softw. 33, 2–14. doi:10.1145/1236463.1236469

  15. [15]

    IFISS: A computational laboratory for investigating incompressible flow problems

    Elman, H.C., Ramage, A., Silvester, D.J., 2014. IFISS: A computational laboratory for investigating incompressible flow problems. SIAM Review 56, 261–273. doi:10.1137/120891393

  16. [16]

    An improved arc algorithm for detecting definite Hermitian pairs

    Guo, C.H., Higham, N.J., Tisseur, F., 2010. An improved arc algorithm for detecting definite Hermitian pairs. SIAM. J. Matrix Anal. Appl. 31, 1131–1151. doi:10.1137/08074218X

  17. [17]

    Computing a nearest symmetric positive semidef- inite matrix

    Higham, N.J., 1988. Computing a nearest symmetric positive semidef- inite matrix. Linear Algebra Appl. 103, 103–118. doi:10.1016/ 0024-3795(88)90223-6

  18. [18]

    Detecting a definite Hermitianpairandahyperbolicorellipticquadraticeigenvalueproblem, and associated nearness problems

    Higham, N.J., Tisseur, F., Van Dooren, P.M., 2002. Detecting a definite Hermitianpairandahyperbolicorellipticquadraticeigenvalueproblem, and associated nearness problems. Linear Algebra Appl. 351–352, 455–

  19. [19]

    doi:https://doi.org/10.1016/S0024-3795(02)00281-1

  20. [20]

    Novel reformulations and efficient algorithms for the generalized trust region subproblem

    Jiang, R., Li, D., 2019. Novel reformulations and efficient algorithms for the generalized trust region subproblem. SIAM J. Optim. 29, 1603– –1633. doi:10.1137/18m1174313

  21. [21]

    SOCP reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices

    Jiang, R., Li, D., Wu, B., 2018. SOCP reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices. Math. Program. 169, 531–563. doi:10.1007/s10107-017-1145-4

  22. [22]

    A subspace method for large-scale eigenvalue optimization

    Kangal, F., Meerbergen, K., Mengi, E., Michiels, W., 2018. A subspace method for large-scale eigenvalue optimization. SIAM J. Matrix Anal. Appl. 39, 48–82. doi:10.1137/16M1070025

  23. [23]

    Nonsmooth algorithms for minimizing the largest eigenvalue with applications to inner numerical radius

    Kangal, F., Mengi, E., 2020. Nonsmooth algorithms for minimizing the largest eigenvalue with applications to inner numerical radius. IMA J. Numer. Anal. 40, 2342–2376. doi:10.1093/imanum/drz041. 35

  24. [24]

    Divide-et-Impera-Verfahren für das verallgemeinerte Eigenwertproblem

    Keller, D., 1994. Divide-et-Impera-Verfahren für das verallgemeinerte Eigenwertproblem. Ph.D. thesis. FernUniversität-Gesamthochschule- Hagen. In German

  25. [25]

    Knyazev , title =

    Knyazev, A.V., 2001. Toward the optimal preconditioned eigensolver: locally optimal block preconditioned conjugate gradient method. SIAM J. Sci. Comput. 23, 517–541. doi:10.1137/S1064827500366124

  26. [26]

    Trace minimization and definiteness of symmetric pencils

    Kovač-Striko, J., Veselić, K., 1995. Trace minimization and definiteness of symmetric pencils. Linear Algebra Appl. 216, 139–158. doi:10.1016/ 0024-3795(93)00126-K

  27. [27]

    Subspace acceleration for the Crawford number and related eigenvalue optimization problems

    Kressner, D., Lu, D., Vandereycken, B., 2018. Subspace acceleration for the Crawford number and related eigenvalue optimization problems. SIAM J. Matrix Anal. Appl. 39, 961–982. doi:10.1137/17M1127545

  28. [28]

    An indefinite vari- ant of LOBPCG for definite matrix pencils

    Kressner, D., Miloloža Pandur, M., Shao, M., 2014. An indefinite vari- ant of LOBPCG for definite matrix pencils. Numer. Algorithms 66, 681–703. doi:10.1007/s11075-013-9754-3

  29. [29]

    Canonical forms for Hermitian matrix pairs under strict equivalence and congruence

    Lancaster, P., Rodman, L., 2005. Canonical forms for Hermitian matrix pairs under strict equivalence and congruence. SIAM Rev. 47, 407–443. doi:10.1137/S003614450444556X

  30. [30]

    Trace minimization principles for positive semi-definite pencils

    Liang, X., Li, R.C., Bai, Z., 2013. Trace minimization principles for positive semi-definite pencils. Linear Algebra Appl. 438, 3085–3106. doi:10.1016/j.laa.2012.12.003

  31. [31]

    and Parlett, B

    Liesen, J., Parlett, B.N., 2008. On nonsymmetric saddle point matrices that allow conjugate gradient iterations. Numer. Math. 108, 605–624. doi:10.1007/s00211-007-0131-9

  32. [32]

    Nonlinear eigenvector methods for convex minimization over the numerical range

    Lu, D., 2020. Nonlinear eigenvector methods for convex minimization over the numerical range. SIAM J. Matrix Anal. Appl. 41, 1771–1796. doi:10.1137/18M1234473

  33. [33]

    The high relative accuracy of the HZ method

    Matejaš, J., Hari, V., 2022. The high relative accuracy of the HZ method. Appl. Math. Comput. 433, 127358. doi:10.1016/j.amc.2022. 127358. 36

  34. [34]

    Quadratic convergence estimate of scaled iterates by J-symmetric Jacobi method

    Matejaš, J., Hari, V., 2006. Quadratic convergence estimate of scaled iterates by J-symmetric Jacobi method. Linear Algebra Appl. 417, 434–465. doi:10.1016/j.laa.2004.01.017. Special issue in honor of Friedrich Ludwig Bauer

  35. [35]

    Numerical optimization of eigenvalues of Hermitian matrix functions

    Mengi, E., Yildirim, E.A., Kiliç, M., 2014. Numerical optimization of eigenvalues of Hermitian matrix functions. SIAM J. Matrix Anal. Appl. 35, 699–724. doi:10.1137/130933472

  36. [36]

    Computing interior eigenvalues and corre- sponding eigenvectors of definite matrix pairs

    Miloloža Pandur, M., 2016. Computing interior eigenvalues and corre- sponding eigenvectors of definite matrix pairs. Ph.D. thesis. Faculty of Science, Department of Mathematics, University of Zagreb, Zagreb. In Croatian

  37. [37]

    Preconditioned gradient iterations for the eigenproblem of definite matrix pairs

    Miloloža Pandur, M., 2019. Preconditioned gradient iterations for the eigenproblem of definite matrix pairs. Electron. Trans. Numer. Anal. 51, 331–362. doi:10.1553/etna_vol51s331

  38. [38]

    Detecting a hyperbolic quadratic eigenvalue problem by using a subspace algorithm

    Miloloža Pandur, M., 2020. Detecting a hyperbolic quadratic eigenvalue problem by using a subspace algorithm. Numer. Algorithms 83, 767–787. doi:10.1007/s11075-019-00702-0

  39. [39]

    Detecting large def- inite Hermitian matrix pairs byθ-subspace algorithms

    Miloloža Pandur, M., Kuzmanović Ivičić, I., 2025. Detecting large def- inite Hermitian matrix pairs byθ-subspace algorithms. BIT Numer. Math. 65, 1–24. doi:10.1007/s10543-025-01082-9

  40. [40]

    AnindefiniteLOBPCGtypeofalgorithmfor detecting a definite Hermitian matrix pair: MATLAB codes

    MiloložaPandur, M., 2026. AnindefiniteLOBPCGtypeofalgorithmfor detecting a definite Hermitian matrix pair: MATLAB codes. Mendeley Data, V2 doi:10.17632/d4gt5kr53k.2

  41. [41]

    Generalizations of the trust region problem

    Moré, J.J., 1993. Generalizations of the trust region problem. Optim. Methods Softw. 2, 189–209. doi:10.1080/10556789308805542

  42. [42]

    Physiological noise and signal-to-noise ratio in fMRI with multi-channel array coils

    Niendorf, V., Voss, H., 2010. Detecting hyperbolic and definite matrix polynomials. Linear Algebra Appl. 432, 1017–1035. doi:10.1016/j. laa.2009.10.014

  43. [43]

    Three-level parallel J-Jacobi algorithms for Hermitian matrices

    Singer, S., Singer, S., Novaković, V., Davidović, D., Bokulić, K., Ušćum- lić, A., 2012. Three-level parallel J-Jacobi algorithms for Hermitian matrices. Appl. Math. Comput. 218, 5704–5725. doi:10.1016/j.amc. 2011.11.067. 37

  44. [44]

    Highly accurate symmetric eigenvalue decomposition and hyperbolic SVD

    Slapničar, I., 2003. Highly accurate symmetric eigenvalue decomposition and hyperbolic SVD. Linear Algebra Appl. 358, 387–424. doi:10.1016/ S0024-3795(02)00516-5

  45. [45]

    Accurate Symmetric Eigenreduction by a Jacobi Method

    Slapničar, I., 1992. Accurate Symmetric Eigenreduction by a Jacobi Method. Ph.D. thesis. FernUniversität-Gesamthochschule, Hagen

  46. [46]

    Componentwise analysis of direct factorization of real symmetric and hermitian matrices

    Slapničar, I., 1998. Componentwise analysis of direct factorization of real symmetric and hermitian matrices. Linear Algebra Appl. 272, 227–

  47. [47]

    doi:10.1016/S0024-3795(97)00334-0

  48. [48]

    Perturbation bounds for the definite generalized eigenvalue problem

    Stewart, G., 1979. Perturbation bounds for the definite generalized eigenvalue problem. Linear Algebra Appl. 23, 69–85. doi:10.1016/ 0024-3795(79)90094-6

  49. [49]

    A conjugate gradient-based algorithm for large-scale quadratic programming problem with one quadratic constraint

    Taati, A., Salahi, M., 2019. A conjugate gradient-based algorithm for large-scale quadratic programming problem with one quadratic constraint. Comput. Optim. Appl. 74, 195–223. doi:10.1007/ s10589-019-00105-w

  50. [50]

    A Jacobi eigenreduction algorithm for definite matrix pairs

    Veselić, K., 1993. A Jacobi eigenreduction algorithm for definite matrix pairs. Numer. Math. 64, 241–269. doi:10.1007/BF01388689. 38