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
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.
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
- 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.
Referee Report
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)
- [§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.
- [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)
- The abstract refers to 'some other algorithms' without naming them; the introduction should explicitly list the competing methods used in the timing comparisons.
- 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
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
-
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
-
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
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
free parameters (1)
- m
Reference graph
Works this paper leans on
-
[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]
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]
Betcke, T., Higham, N.J., Mehrmann, V., Schröder, C., Tisseur, F.,
-
[4]
NLEVP: A collection of nonlinear eigenvalue problems. ACM Trans. Math. Software 39, 1–28. doi:10.1145/2427023.2427024
-
[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]
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–
2006
-
[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]
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]
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]
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–
1983
-
[11]
doi:10.1016/0024-3795(83)90148-9
-
[12]
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]
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
1993
-
[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]
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]
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]
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
1988
-
[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–
2002
-
[19]
doi:https://doi.org/10.1016/S0024-3795(02)00281-1
-
[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]
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]
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]
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]
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
1994
-
[25]
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]
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
1995
-
[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]
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]
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]
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]
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]
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]
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]
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]
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]
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
2016
-
[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]
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]
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]
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]
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]
A Dynamic Recursive Unified Internet Design (DRUID),
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
work page doi:10.1016/j 2010
-
[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]
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
2003
-
[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
1992
-
[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–
1998
-
[47]
doi:10.1016/S0024-3795(97)00334-0
-
[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
1979
-
[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
2019
-
[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
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.