An efficient algorithm for the minimal least squares solution of linear systems with indefinite symmetric matrices. (English) Zbl 07866496
Summary: In this work, a new algorithm for solving symmetric indefinite systems of linear equations is presented. It factorizes the matrix into the form \(LDL^t\) using Jacobi rotations in order to increase the pivot’s absolute value. Furthermore, Rook’s pivoting strategy is also adapted and implemented. In determinate compatible systems, the computational cost of the algorithm was similar to the cost of the Bunch-Kaufman method, but the error was approximately 50% smaller for intermediate and large matrices, regardless of the condition number of the coefficient matrix. Furthermore, unlike Bunch-Kaufman, the new algorithm calculates with little additional cost the fundamental basis of the null space, and obtains the minimal least squares and minimum norm solutions. In minimal least squares with minimum norm problems, the new algorithm was compared with the LAPACK Complete Orthogonal Decomposition algorithm, among others. The obtained error with both algorithms was similar but the computational cost was at least 20% smaller with the new algorithm, even though the Complete Orthogonal Decomposition is implemented in a blocked form.
Keywords:
symmetric indefinite matrix; least squares solution; \(LDL^t\) factorization; Bunch-Kaufman; diagonal pivoting method; Jacobi rotationsSoftware:
MersenneTwisterReferences:
| [1] | Bunch, JR.; Kauffman, L., Some stable methods for calculating inertia and solving symmetric linear systems, Math. Comput., 31, 163-179, (1977) · Zbl 0355.65023 |
| [2] | Ashcraft, C.; Grimes, RG.; Lewis, JG., Accurate symmetric indefinite linear equation solvers, SIAM J. Matrix Anal. App., 20, 513-561, (1998) · Zbl 0923.65010 |
| [3] | Higham, NJ., Stability of the diagonal pivoting method with partial pivoting, SIAM J. Matrix Anal. App., 18, 52-65, (1997) · Zbl 0884.65024 |
| [4] | Bunch, JR.; Parlett, B. N., Direct methods for solving symmetric indefinite systems of linear equations, SIAM J. Matrix Anal. App., 8, 639-655, (1971) · Zbl 0199.49802 |
| [5] | Golub, GH.; Van Loan, CF., Matrix Computations, (1996), John Hopkins University Press: John Hopkins University Press Baltimore · Zbl 0865.65009 |
| [6] | Fernández de Bustos, I.; García-Marina, V.; Urkullu, G.; Abasolo, M., An efficient LDU algorithm for the minimal least squares solution of linear systems, J. Comput. Appl. Math., 344, 346-355, (2018) · Zbl 1398.65034 |
| [7] | Fernández de Bustos, I.; Agirrebeitia, J.; Ajuria, G.; Ansola, R., An alternative full-pivoting algorithm for the factorization of indefinite symmetric matrices, J. Comput. Appl. Math., 274, 44-57, (2015) · Zbl 1296.65047 |
| [8] | Peters, G.; Wilkinson, JH., The least squares problem and pseudo-inverses, Comput. J., 13, 309-316, (1970) · Zbl 0195.44804 |
| [9] | Sautter, W., Fehleranalyse für die Gauß-Elimination zur Berechnung der Lösung minimaler Länge, Numer. Math., 30, 165-184, (1978) · Zbl 0425.65024 |
| [10] | Foster, LV., The growth factor and efficiency of Gaussian elimination with rook pivoting, J. Comput. Appl. Math., 86, 177-194, (1997) · Zbl 0903.65021 |
| [11] | Poole, G.; Neal, L., The Rook’s pivoting strategy, J. Comput. Appl. Math., 123, 353-369, (2000) · Zbl 0964.65027 |
| [12] | Neal, L.; Poole, G., A geometric analysis of gaussian elimination II, Linear. Algebra Appl., 173, 239-264, (1992) · Zbl 0765.65036 |
| [13] | Hammarling, S., A Survey of Numerical Aspects of Plane Rotations, MIMS EPrint 2008.69, (1977), Manchester Institute for Mathematical Sciences, University of Manchester |
| [14] | Wilkinson, JH., Error analysis of direct methods of matrix inversion, Journal of the ACM, 8, 281-330, (1961) · Zbl 0109.09005 |
| [15] | Higham, DJ.; Higham, NJ.; Pranesh, S., Random matrices generating large growth in LU factorization with pivoting, SIAM J. Matrix Anal. App., 42, 185-201, (2021) · Zbl 1459.65036 |
| [16] | Druinsky, A.; Toledo, S., The growth-factor bound for the Bunch-Kaufman factorization is tight, SIAM J. Matrix Anal. App., 32, 928-937, (2011) · Zbl 1242.65054 |
| [17] | Coleman, TF.; Pothen, A., The null space problem I. Complexity, SIAM J. Algebr. Discrete Methods, 7, 527-537, (1986) · Zbl 0608.65024 |
| [18] | Stewart, G. W., The efficient generation of random orthogonal matrices with an application to condition estimators, SIAM J. Numer. Anal., 17, 3, 403-409, (1980) · Zbl 0443.65027 |
| [19] | Matsumoto, M.; Nishimura, T., Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Trans. Model. Comput. Simul., 8, 1, 3-30, (1998) · Zbl 0917.65005 |
| [20] | Box, G. E.; Muller, M. E., A note on the generation of random normal deviates, Ann. Math. Stat., 29, 2, 610-611, (1958) · Zbl 0085.13720 |
| [21] | MacDougall, M., Simulating Computer Systems: Techniques and Tools, (1987) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
