×

A block algorithm for computing antitriangular factorizations of symmetric matrices. (English) Zbl 1333.65043

Summary: Any symmetric matrix can be reduced to antitriangular form in finitely many steps by orthogonal similarity transformations. This form reveals the inertia of the matrix and has found applications in, e.g., model predictive control and constraint preconditioning. Originally proposed by N. Mastronardi and P. van Dooren [SIAM J. Matrix Anal. Appl. 34, No. 1, 173–196 (2013; Zbl 1272.65031)], the existing algorithm for performing the reduction to antitriangular form is primarily based on Householder reflectors and Givens rotations. The poor memory access pattern of these operations implies that the performance of the algorithm is bound by the memory bandwidth. In this work, we develop a block algorithm that performs all operations almost entirely in terms of level 3 BLAS operations, which feature a more favorable memory access pattern and lead to better performance. These performance gains are confirmed by numerical experiments that cover a wide range of different inertia.

MSC:

65F30 Other matrix algorithms (MSC2010)
65F08 Preconditioners for iterative methods
65F25 Orthogonalization in numerical linear algebra
65Y20 Complexity and performance of numerical algorithms

Citations:

Zbl 1272.65031
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Auckenthaler, T., Blum, V., Bungartz, H.J., Huckle, T., Johanni, R., Krämer, L., Lang, B., Lederer, H., Willems, P.: Parallel solution of partial symmetric eigenvalue problems from electronic structure calculations. Parallel Comput. 37(12), 783-794 (2011) · doi:10.1016/j.parco.2011.05.002
[2] Bientinesi, P., Igual, F.D., Kressner, D., Petschow, M., Quintana-Ortí, E.S.: Condensed forms for the symmetric eigenvalue problem on multi-threaded architectures. Concurr. Comput.: Pract. Experience 23(7), 694-707 (2011) · doi:10.1002/cpe.1680
[3] Bischof, C.H., Quintana-Ortí, G.: Computing rank-revealing QR factorizations of dense matrices. ACM Trans. Math. Softw. 24(2), 226-253 (1998) · Zbl 0932.65033 · doi:10.1145/290200.287637
[4] Buttari, A., Langou, J., Kurzak, J., Dongarra, J.: A class of parallel tiled linear algebra algorithms for multicore architectures. Parallel Comput. 35(1), 38-53 (2009) · doi:10.1016/j.parco.2008.10.002
[5] Davis, T.A.: Algorithm 915, SuiteSparseQR: multifrontal multithreaded rank-revealing sparse QR factorization. ACM Trans. Math. Softw. 38(1) (2011). Art. 8, 22 · Zbl 1365.65122
[6] Drmaċ, Z., Bujanović, Z.: On the failure of rank-revealing QR factorization software—a case study. ACM Trans. Math. Softw. 35(2) (2009). Art. 12, 28 · Zbl 0932.65033
[7] Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd. Johns Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[8] Haidar, A., Ltaief, H., Dongarra, J.: Parallel reduction to condensed forms for symmetric eigenvalue problems using aggregated fine-grained and memory-aware kernels. In: Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, SC ’11, pp 8:1-8:11. ACM, NY, USA (2011)
[9] Haidar, A., Solcà, R., Gates, M., Tomov, S., Schulthess, T., Dongarra, J.: Leading edge hybrid multi-GPU algorithms for generalized eigenproblems in electronic structure calculations. In: Kunkel, J., Ludwig, T., Meuer, H. (eds.) Supercomputing, Lecture Notes in Computer Science, vol. 7905, pp 67-80. Springer Berlin Heidelberg (2013) · Zbl 0932.65033
[10] Mastronardi, N., Van Dooren, P.: Recursive approximation of the dominant eigenspace of an indefinite matrix. J. Comput. Appl. Math. 236(16), 4090-4104 (2012) · Zbl 1246.65061 · doi:10.1016/j.cam.2012.02.032
[11] Mastronardi, N., Van Dooren, P.: The antitriangular factorization of symmetric matrices. SIAM J. Matrix Anal. Appl. 34(1), 173-196 (2013) · Zbl 1272.65031 · doi:10.1137/110858860
[12] Mastronardi, N., Van Dooren, P.: On solving KKT linear systems with antitriangular matrices (2013). TUM-IAS Workshop on Novel Numerical Methods, Munich Germany. Presentation available from http://www.tum-ias.de/fileadmin/material_ias/pdf/NoNuMe/Presentations/Paul_van_Dooren.pdf · Zbl 1272.65031
[13] Mastronardi, N., Van Dooren, P.: An algorithm for solving the indefinite least squares problem with equality constraints. BIT 54(1), 201-218 (2014) · Zbl 1290.65033 · doi:10.1007/s10543-013-0452-2
[14] Mastronardi, N., Van Dooren, P., Vandebril, R.: On solving KKT linear systems arising in model predictive control via recursive antitriangular factorization (2014). Presentation at Householder Symposium XIX, 8-13, Spa, Belgium
[15] Parlett, B.N.: The Symmetric Eigenvalue Problem. Society for Industrial and Applied Mathematics (1998) · Zbl 0885.65039
[16] Pestana, J., Wathen, A.J.: The antitriangular factorization of saddle point matrices. SIAM J. Matrix Anal. Appl. 35(2), 339-353 (2014) · Zbl 1385.65027 · doi:10.1137/130934933
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.