# zbMATH — the first resource for mathematics

Parallel QR factorization of block-tridiagonal matrices. (English) Zbl 1457.65018
##### MSC:
 65F05 Direct numerical methods for linear systems and matrix inversion 65F20 Numerical solutions to overdetermined systems, pseudoinverses 65Y05 Parallel numerical computation
##### Keywords:
QR factorization; task based parallelism; nested dissection
##### Software:
CSparse; SPIKE; StarPU; SuiteSparseQR; SuitSparseQR
Full Text:
##### References:
 [1] E. Agullo, A. Buttari, A. Guermouche, and F. Lopez, Implementing multifrontal sparse solvers for multicore architectures with sequential task flow runtime systems, ACM Trans. Math. Software, 43 (2016), 13, https://doi.acm.org/10.1145/2898348. · Zbl 1369.65062 [2] P R. Amestoy, I S. Duff, and C Puglisi, Multifrontal QR factorization in a multiprocessor environment, Int. J. Numer. Linear Alg. Appl., 3 (1996), pp. 275-300, https://doi.org/10.1002/(SICI)1099-1506(199607/08)3:4<275::AID-NLA83>3.0.CO;2-7. · Zbl 0907.65040 [3] P. Arbenz and M. Hegland, On the stable parallel solution of general narrow banded linear systems, in High Performance Algorithms for Structured Matrix Problems, Adv. Theory Comput. Math. 2, Nova Science Publishers, Commack, NY, pp. 47-73. · Zbl 0930.65017 [4] G. Arvanitidis, L. K. Hansen, and S. Hauberg, Latent space oddity: On the curvature of deep generative models, in Proceedings of the International Conference on Learning Representations (ICLR), 2018. [5] C. Augonnet, S. Thibault, R. Namyst, and P.-A. Wacrenier, StarPU: A unified platform for task scheduling on heterogeneous multicore architectures, Concurrency Computation Practice Experience, 23 (2011), pp. 187-198, https://doi.org/10.1002/cpe.1631. [6] Y. Bengio, A. Courville, and P. Vincent, Representation learning: A review and new perspectives, IEEE Trans. Pattern Anal. Mach. Intell., 35 (2013), pp. 1798-1828. [7] M. W. Berry and A. Sameh, Multiprocessor schemes for solving block tridiagonal linear systems, Int. J. Supercomputing Appl., 2 (1988), pp. 37-57, https://doi.org/10.1177/109434208800200304. [8] H. Bouwmeester, M. Jacquelin, J. Langou, and Y. Robert, Tiled QR factorization algorithms, in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, ACM, 2011, https://doi.org/10.1145/2063384.2063393. [9] A. Buttari, Fine-grained multithreading for the multifrontal QR factorization of sparse matrices, SIAM J. Sci. Comput., 35, pp. C323-C345, https://doi.org/10.1137/110846427. · Zbl 1362.65031 [10] A. Buttari, J. Langou, J. Kurzak, and J. Dongarra, A class of parallel tiled linear algebra algorithms for multicore architectures, Parallel Comput., 35 (2009), pp. 38-53, https://doi.org/10.1016/j.parco.2008.10.002. [11] T. Davis, Direct Methods for Sparse Linear Systems, Fundam. Algorithms 2, SIAM, Philadelphia, 2006, https://doi.org/10.1137/1.9780898718881. [12] T. A. Davis, Algorithm $$915$$, SuiteSparseQR: Multifrontal multithreaded rank-revealing sparse QR factorization, ACM Trans. Math. Software, 38 (2011), 8, https://doi.org/10.1145/2049662.2049670. · Zbl 1365.65122 [13] J. Demmel, L. Grigori, M. Hoemmen, and J. Langou, Communication-optimal parallel and sequential QR and LU factorizations, SIAM J. Sci. Comput., 34 (2012), pp. 206-239, https://doi.org/10.1137/080731992. · Zbl 1241.65028 [14] I. S. Duff, A. M. Erisman, and J. K Reid, Direct Methods for Sparse Matrices, Oxford University Press, Oxford, UK, 2017. · Zbl 1364.65067 [15] W. M. Gentleman, Row elimination for solving sparse linear systems and least squares problems, in Numerical Analysis, G. Alistair Watson, ed., Springer, Berlin, pp. 122-133, https://doi.org/10.1007/BFb0080119. [16] A. J. George, Nested dissection of a regular finite-element mesh, SIAM J. Numer. Anal., 10 (1973), pp. 345-363, https://doi.org/10.1137/0710032. · Zbl 0259.65087 [17] A. J. George and M. T. Heath, Solution of sparse linear least squares problems using Givens rotations, Linear Algebra Appl., 34 (1980), pp. 69-83. · Zbl 0459.65025 [18] S. Hauberg, Only Bayes Should Learn a Manifold, arXiv:1806.04994, 2018. [19] M. Hegland, On the parallel solution of tridiagonal systems by wrap-around partitioning and incomplete LU factorization, Numer. Math., 59 (1991), pp. 453-472, https://doi.org/10.1007/BF01385791. · Zbl 0738.65015 [20] M. Hegland and M. Osborne, Algorithms for block bidiagonal systems on vector and parallel computers, in Proceedings of the 12th International Conference on Supercomputing, ACM, 1998, pp. 1-6, https://doi.org/10.1145/277830.277835. [21] R. W. Hockney, A fast direct solution of Poisson’s equation using Fourier analysis, J. ACM, 12 (1965), pp. 95-113, https://doi.org/10.1145/321250.321259. · Zbl 0139.10902 [22] J. W. H. Liu, On general row merging schemes for sparse Givens transformations, SIAM J. Sci. Stat. Comput., 7 (1986), pp. 1190-1211. · Zbl 0605.65031 [23] J. W. H. Liu, The role of elimination trees in sparse factorization, SIAM J. Matrix Anal. Appl., 11 (1990), pp. 134-172, https://doi.org/10.1137/0611010. · Zbl 0697.65013 [24] OpenMP Architecture Review Board, OpenMP 5.0, Complete Specifications, 2018. [25] E. Polizzi and A. H. Sameh, A parallel hybrid banded system solver: The SPIKE algorithm, Parallel Comput., 32 (2006), pp. 177-194, https://doi.org/10.1016/j.parco.2005.07.005, [26] D. J. Rose, R. E. Tarjan, and G. S. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5 (1976), pp. 266-283, https://doi.org/10.1137/0205021. · Zbl 0353.65019 [27] A. Sameh, On two numerical algorithms for multiprocessors, in Proceedings of the NATO Advanced Research Workshop on High-Speed Computing, Series F: Computer and Systems Sciences, Vol. 7, Springer, Berlin, 1984, pp. 311-328. [28] A. H. Sameh and D. J. Kuck, On stable parallel linear system solvers, J. ACM, 25 (1976), pp. 81-91, https://doi.org/10.1145/322047.322054. · Zbl 0364.68051
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.