×

zbMATH — the first resource for mathematics

Look-ahead in the two-sided reduction to compact band forms for symmetric eigenvalue problems and the SVD. (English) Zbl 1415.65090
Summary: We address the reduction to compact band forms, via unitary similarity transformations, for the solution of symmetric eigenvalue problems and the computation of the singular value decomposition (SVD). Concretely, in the first case, we revisit the reduction to symmetric band form, while, for the second case, we propose a similar alternative, which transforms the original matrix to (unsymmetric) band form, replacing the conventional reduction method that produces a triangular-band output. In both cases, we describe algorithmic variants of the standard Level 3 Basic Linear Algebra Subroutines (BLAS)-based procedures, enhanced with look-ahead, to overcome the performance bottleneck imposed by the panel factorization. Furthermore, our solutions employ an algorithmic block size that differs from the target bandwidth, illustrating the important performance benefits of this decision. Finally, we show that our alternative compact band form for the SVD is key to introduce an effective look-ahead strategy into the corresponding reduction procedure.
MSC:
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F30 Other matrix algorithms (MSC2010)
65Y05 Parallel numerical computation
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aliaga, JI; Alonso, P.; Badía, JM; Chacn, P.; Davidović, D.; López-Blanco, JR; Quintana-Ortí, ES, A fast band-krylov eigensolver for macromolecular functional motion simulation on multicore architectures and graphics processors, J. Comput. Phys., 309, 314-323, (2016) · Zbl 1352.65200
[2] Anderson, E., Bai, Z., Blackford, L.S., Demmel, J., Dongarra, J.J., Du Croz, J., Hammarling, S., Greenbaum, A., McKenney, A., Sorensen, D.C.: LAPACK Users’ Guide, 3rd edn. SIAM (1999) · Zbl 0934.65030
[3] Ballard, G.; Demmel, J.; Grigori, L.; Jacquelin, M.; Knight, N.; Nguyen, HD, Reconstructing householder vectors from tall-skinny QR, J. Parallel Distributed Comp., 85, 3-31, (2015)
[4] Bientinesi, P.; Igual, FD; Kressner, D.; Petschow, M.; Quintana-ortí, ES, Condensed forms for the symmetric eigenvalue problem on multi-threaded architectures, Concurrency Comp.: Pract. Exp., 23, 694-707, (2011)
[5] Bischof, CH; Lang, B.; Sun, X., Algorithm 807: the SBR Toolbox—software for successive band reduction, ACM Trans. Math. Soft., 26, 602-616, (2000) · Zbl 1365.65104
[6] Buttari, A.; Langou, J.; Kurzak, J.; Dongarra, J., A class of parallel tiled linear algebra algorithms for multicore architectures, Parallel Comput., 35, 38-53, (2009)
[7] Castaldo, AM; Whaley, RC; Samuel, S., Scaling LAPACK panel operations using parallel cache assignment, ACM Trans. Math. Soft., 39, 22:1-22:30, (2013) · Zbl 1295.65135
[8] Catalȧn, S., Herrero, J.R., Quintana-ortí, E.S., Rodríguez-Sȧnchez, R., van de Geijn, R.A.: A case for malleable thread-level linear algebra libraries: The LU factorization with partial pivoting. CoRR, arXiv:1611.06365 (2016)
[9] Davidović, D., Quintana-Ortí, E.S.: Applying OOC techniques in the reduction to condensed form for very large symmetric eigenproblems on GPUs. In: Proceedings of the 20th Euromicro Conference on Parallel, Distributed and Network Based Processing - PDP 2012, pp. 442-449 (2012)
[10] Davis, T.A., Rajamanickam, S.: Algorithm 8xx: PIRO BAND, pipelined plane rotations for band reduction. ACM Trans. Math. Soft. Submitted
[11] Dhillon, IS; Parlett, BN; Vömel, C., The design and implementation of the MRRR algorithm, ACM Trans. Math. Softw., 32, 533-560, (2006) · Zbl 1230.65046
[12] Dongarra, JJ; Du Croz, J.; Hammarling, S.; Duff, I., A set of level 3 basic linear algebra subprograms, ACM Trans. Math. Softw., 16, 1-17, (1990) · Zbl 0900.65115
[13] Dongarra, JJ; Croz, JD; Hammarling, S.; Hanson, RJ, An extended set of FORTRAN basic linear algebra subprograms, ACM Trans. Math. Softw., 14, 1-17, (1988) · Zbl 0639.65016
[14] Fernando, KV; Parlett, BN, Accurate singular values and differential QD algorithms, Numer. Mathematik, 67, 191-229, (1994) · Zbl 0814.65036
[15] Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. The Johns Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[16] Grosser, B.; Lang, B., Efficient parallel reduction to bidiagonal form, Parallel Comput., 25, 969-986, (1999) · Zbl 1062.65503
[17] Gu, M.; Eisenstat, SC, Divide-and-conquer algorithm for the bidiagonal SVD, SIAM J. Matrix Anal. Appl., 16, 79-92, (1995) · Zbl 0821.65019
[18] Haidar, A., Ltaief, H., Dongarra, J.: Parallel reduction to condensed forms for symmetric eigenvalue problems using aggregated fine-grained and memory-aware kernels. In: 2011 International Conference for High Performance Computing, Networking, Storage and Analysis (SC), pp. 1-11 (2011)
[19] Haidar, A., Kurzak, J., Luszczek, P.: An improved parallel singular value algorithm and its implementation for multicore hardware. In: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, SC ’13, pp. 90:1-90:12. ACM, New York (2013)
[20] Moldaschl, M.; Gansterer, WN, Comparison of eigensolvers for symmetric band matrices, Sci. Comput. Program., 90, 55-66, (2014)
[21] Petschow, M.; Peise, E.; Bientinesi, P., High-performance solvers for dense Hermitian eigenproblems, SIAM J. Scientific Comp., 35, c1-c22, (2013) · Zbl 1264.65054
[22] Quintana-Ortí, G.; Quintana-Ortí, ES; de Geijn, RA; Zee, FG; Chan, E., Programming matrix algorithms-by-blocks for thread-level parallelism, ACM Trans. Math. Softw., 36, 14:1-14:26, (2009) · Zbl 1364.65105
[23] Strazdins, P.: A comparison of lookahead and algorithmic blocking techniques for parallel matrix factorization. Technical Report TR-CS-98-07, Department of Computer Science, The Australian National University Canberra 0200 ACT, Australia (1998)
[24] Zee, FG; Smith, TM; Marker, B.; Low, TM; De Geijn, RA; Igual, FD; Smelyanskiy, M.; Zhang, X.; Kistler, M.; Austel, V.; Gunnels, JA; Killough, L., The BLIS framework: experiments in portability, ACM Trans. Math. Softw., 42, 12:1-12:19, (2016)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.