×

Randomized complete pivoting for solving symmetric indefinite linear systems. (English) Zbl 1404.65013

Summary: The Bunch-Parlett algorithm, the Bunch-Kaufman algorithm, the bounded Bunch-Kaufman algorithm, and Aasen’s algorithm are four well-known methods for solving symmetric indefinite linear systems, yet the last three methods are known to suffer from potential numerical instability. In this work, we develop a randomized complete pivoting (RCP) algorithm for solving symmetric indefinite linear systems of equations. RCP is comparable to the Bunch-Kaufman algorithm and Aasen’s algorithm in computational efficiency, but still enjoys theoretical element growth and bounded entries in the factorization comparable to that of the Bunch-Parlett algorithm, up to a theoretical failure probability that exponentially decays with an oversampling parameter. In terms of the boundedness of entries in \(L\), the Bunch-Parlett algorithm, the bounded Bunch-Kaufman algorithm, and Aasen’s algorithm have \(\max_{i<j}| l_{ji}|=1\), while the Bunch-Kaufman algorithm does not have a bound. Although we show that RCP only has \(\max_{i<j}| l_{ji}|=O(\sqrt{n})\) in theory, our experiments show that this bound is actually \(O(1)\). Our finite precision analysis shows that RCP is as numerically stable as Gaussian elimination with complete pivoting, and RCP has been observed to be numerically stable in our extensive numerical experiments.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
15A06 Linear equations (linear algebraic aspects)
15A23 Factorization of matrices
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] J. O. Aasen, On the reduction of a symmetric matrix to tridiagonal form, Nordisk Tidskr. Informationsbehandling (BIT), 11 (1971), pp. 233–242. · Zbl 0242.65032
[2] E. Anderson, Z. Bai, C. Bischof, L. S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen, LAPACK Users’ Guide, SIAM, Philadelphia, 1999, .
[3] M. Arioli, M. Baboulin, and S. Gratton, A partial condition number for linear least squares problems, SIAM J. Matrix Anal. Appl., 29 (2007), pp. 413–433, . · Zbl 1141.65028
[4] R. I. Arriaga and S. Vempala, An algorithmic theory of learning: Robust concepts and random projection, in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1999, pp. 616–623. · Zbl 1095.68092
[5] C. Ashcraft, R. G. Grimes, and J. G. Lewis, Accurate symmetric indefinite linear equation solvers, SIAM J. Matrix Anal. Appl., 20 (1998), pp. 513–561, . · Zbl 0923.65010
[6] M. Baboulin, D. Becker, G. Bosilca, A. Danalis, and J. Dongarra, An efficient distributed randomized algorithm for solving large dense symmetric indefinite linear systems, Parallel Comput., 40 (2014), pp. 213–223.
[7] M. Baboulin, J. Dongarra, J. Herrmann, and S. Tomov, Accelerating linear system solutions using randomization techniques, ACM Trans. Math. Software, 39 (2013), no. 2, 8. · Zbl 1295.65134
[8] M. Baboulin, J. Dongarra, A. Rémy, S. Tomov, and I. Yamazaki, Dense symmetric indefinite factorization on GPU accelerated architectures, in Parallel Processing and Applied Mathematics, Springer, Cham, 2016, pp. 86–95.
[9] M. Benzi, G. H. Golub, and J. Liesen, Numerical solution of saddle point problems, Acta Numer., 14 (2005), pp. 1–137. · Zbl 1115.65034
[10] \AA. Björck, Numerical Methods for Least Squares Problems, SIAM, Philadelphia, 1996, .
[11] J. R. Bunch, Analysis of the diagonal pivoting method, SIAM J. Numer. Anal., 8 (1971), pp. 656–680, .
[12] J. R. Bunch and L. Kaufman, Some stable methods for calculating inertia and solving symmetric linear systems, Math. Comp., 31 (1977), pp. 163–179. · Zbl 0355.65023
[13] J. R. Bunch and B. N. Parlett, Direct methods for solving symmetric indefinite systems of linear equations, SIAM J. Numer. Anal., 8 (1971), pp. 639–655, .
[14] P. Businger and G. H. Golub, Linear least squares solutions by Householder transformations, Numer. Math., 7 (1965), pp. 269–276. · Zbl 0142.11503
[15] T. A. Davis and Y. Hu, The University of Florida sparse matrix collection, ACM Trans. Math. Software, 38 (2011), no. 1, 1. · Zbl 1365.65123
[16] I. T. Dimov, Monte Carlo Methods for Applied Scientists, World Scientific, Hackensack, NJ, 2008. · Zbl 1140.65008
[17] J. J. Dongarra, C. B. Moler, J. R. Bunch, and G. W. Stewart, LINPACK Users’ Guide, SIAM, Philadelphia, 1979, .
[18] Z. Drmač and Z. Bujanović, On the failure of rank-revealing QR factorization software—a case study, ACM Trans. Math. Software, 35 (2009), no. 2, 12.
[19] A. Druinsky and S. Toledo, The growth-factor bound for the Bunch-Kaufman factorization is tight, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 928–937, . · Zbl 1242.65054
[20] J. A. Duersch and M. Gu, Randomized QR with column pivoting, SIAM J. Sci. Comput., 39 (2017), pp. C263–C291, . · Zbl 1371.65026
[21] I. S. Duff and S. Pralet, Strategies for scaling and pivoting for sparse symmetric indefinite problems, SIAM J. Matrix Anal. Appl., 27 (2005), pp. 313–340, . · Zbl 1092.65037
[22] I. S. Duff and J. K. Reid, The multifrontal solution of indefinite sparse symmetric linear equations, ACM Trans. Math. Software, 9 (1983), pp. 302–325. · Zbl 0515.65022
[23] Y. Feng and L. Lu, On the Growth Factor Upper Bound for Aasen’s Algorithm, preprint, , 2018.
[24] G. Golub, Numerical methods for solving linear least squares problems, Numer. Math., 7 (1965), pp. 206–216. · Zbl 0142.11502
[25] G. H. Golub and C. F. Van Loan, Matrix Computations, Vol. 3, Johns Hopkins University Press, Baltimore, MD, 2012. · Zbl 1268.65037
[26] M. Gu, Subspace iteration randomization and singular value problems, SIAM J. Sci. Comput., 37 (2015), pp. A1139–A1173, .
[27] N. Halko, P. G. Martinsson, and J. A. Tropp, Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev., 53 (2011), pp. 217–288, . · Zbl 1269.65043
[28] N. J. Higham, Stability of the diagonal pivoting method with partial pivoting, SIAM J. Matrix Anal. Appl., 18 (1997), pp. 52–65, . · Zbl 0884.65024
[29] N. J. Higham, Accuracy and Stability of Numerical Algorithms, SIAM, Philadelphia, 2002, . . · Zbl 1011.65010
[30] N. J. Higham, The Matrix Computation Toolbox, , 2002.
[31] J. D. Hogg and J. A. Scott, Compressed threshold pivoting for sparse symmetric indefinite systems, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 783–817, . · Zbl 1301.65020
[32] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, UK, 2012.
[33] W. B. Johnson and J. Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, in Conference in Modern Analysis and Probability, Contemp. Math. 26, AMS, Providence, RI, 1984, pp. 189–206. · Zbl 0539.46017
[34] C. S. Kenney, A. J. Laub, and M. S. Reese, Statistical condition estimation for linear least squares, SIAM J. Matrix Anal. Appl., 19 (1998), pp. 906–923, . · Zbl 0913.65035
[35] J.-Y. L’Excellent, Multifrontal Methods: Parallelism, Memory Usage and Numerical Aspects, Habilitation à diriger des recherches, École normale supérieure de Lyon, Lyon, France, 2012.
[36] J. W. Liu, A partial pivoting strategy for sparse symmetric matrix decomposition, ACM Trans. Math. Software, 13 (1987), pp. 173–182. · Zbl 0628.65017
[37] M. W. Mahoney, Randomized algorithms for matrices and data, Found. Trends Mach. Learn., 3 (2011), pp. 123–224. · Zbl 1232.68173
[38] P.-G. Martinsson, Blocked Rank-Revealing QR Factorizations: How Randomized Sampling Can Be Used to Avoid Single-Vector Pivoting, preprint, , 2015.
[39] P.-G. Martinsson, G. Quintana Ortí, N. Heavner, and R. van de Geijn, Householder QR factorization with randomization for column pivoting (HQRRP), SIAM J. Sci. Comput., 39 (2017), pp. C96–C115, . · Zbl 1365.65070
[40] P.-G. Martinsson, V. Rokhlin, and M. Tygert, A randomized algorithm for the decomposition of matrices, Appl.Comput. Harmon. Anal., 30 (2011), pp. 47–68. · Zbl 1210.65095
[41] C. Melgaard and M. Gu, Gaussian Elimination with Randomized Complete Pivoting, preprint, , 2015.
[42] J.-C. Nédélec, Acoustic and Electromagnetic Equations: Integral Representations for Harmonic Problems, Appl. Math. Sci. 144, Springer-Verlag, New York, 2001.
[43] J. Nocedal and S. Wright, Numerical Optimization, Springer, New York, 1999. · Zbl 0930.65067
[44] D. S. Parker, Random Butterfly Transformations with Applications in Computational Linear Algebra, Technical Report CSD-950023, Computer Science Department, UCLA, Los Angeles, CA, 1995.
[45] S. Pralet, Constrained Orderings and Scheduling for Parallel Sparse Linear Algebra, Ph.D. thesis, Institut National Polytechnique de Toulouse, Toulouse, France, and CERFACS Technical Report TH/PA/04/105, 2004.
[46] S. S. Vempala, The Random Projection Method, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 65, AMS, Providence, RI, 2004. · Zbl 1058.68063
[47] J. H. Wilkinson, Error analysis of direct methods of matrix inversion, J. Assoc. Comput. Mach., 8 (1961), pp. 281–330. · Zbl 0109.09005
[48] F. Woolfe, E. Liberty, V. Rokhlin, and M. Tygert, A fast randomized algorithm for the approximation of matrices, Appl. Comput. Harmon. Anal., 25 (2008), pp. 335–366. · Zbl 1155.65035
[49] J. Xiao and M. Gu, Spectrum-revealing Cholesky factorization for kernel methods, in Proceedings of the 16th IEEE International Conference on Data Mining (ICDM), 2016, pp. 1293–1298.
[50] J. Xiao, M. Gu, and J. Langou, Fast parallel randomized QR with column pivoting algorithms for reliable low-rank matrix approximations, in Proceedings of the 24th IEEE International Conference on High Performance Computing (HiPC), 2017, pp. 233–242.
[51] D. Zwillinger and S. Kokoska, CRC Standard Probability and Statistics Tables and Formulae, Chapman & Hall/CRC, Boca Raton, FL, 1999.
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.