Divide and Conquer Methods for Solving Linear Systems
DOI:
https://doi.org/10.26713/cma.v14i2.2129Keywords:
Divide and conquer, Recursive algorithm, Schur complement, Matrix decomposition, Matrix inversionAbstract
The Divide and Conquer (D&C) strategy solves a problem by breaking it down into subproblems, which are themselves smaller cases of the same type of problem. We will see how this technique creates a numerical recursive algorithm to calculate the inverse of square matrices and solve linear systems using Schur’s complement, Cholesky, and LU decomposition.
Downloads
References
A. M. Abu-Saman, Computing matrix inverses by divide-and-conquer method with floating point calculations, International Journal of Computational and Applied Mathematics 7(4) (2012), 479 – 484.
A. M. Abu-Saman and S. S. El-Okur, Divide-and-conquer strategy with Cholesky’s factorization for inverting symmetric positive definite matrices, International Electronic Journal of Pure and Applied Mathematics 7(2) (2014), 53 – 62, DOI: 10.12732/iejpam.v7i2.1.
B. S. Andersen, F. Gustavson, A. Karaivanov, M. Marinova, J. Wasniewski and P. Yalamov, LAWRA Linear Algebra with Recursive Algorithms, in: Applied Parallel Computing. New Paradigms for HPC in Industry and Academia (PARA 2000), T. Sørevik, F. Manne, A. H. Gebremedhin and R. Moe (editors), Lecture Notes in Computer Science, Vol. 1947, Springer, Berlin — Heidelberg (2001), DOI: 10.1007/3-540-70734-4_7.
S. Banerjee and A. Roy, Linear Algebra and Matrix Analysis for Statistics, 1st edition, Chapman and Hall/CRC, New York, 580 pages (2014), DOI: 10.1201/b17040.
Å. Björck, Numerical Methods in Matrix Computations, 1st edition, Texts in Applied Mathematics series, Vol. 59, Springer Cham, xvi + 800 pages (2015), DOI: 10.1007/978-3-319-05089-8.
A. Cleary and J. Dongarra, Implementation in ScaLAPACK of Divide-and-Conquer Algorithms for Banded and Tridiagonal Linear Systems, Technical Report UT-CS-97-358, University of Tennessee, Knoxville, TN, (1997), URL: https://library.eecs.utk.edu/files/ut-cs-97-358.pdf.
J.-J. Climent, C. Perea, L. Tortosa and A. Zamora, A BSP recursive divide and conquer algorithm to solve a tridiagonal linear system, Applied Mathematics and Computation 159(2) (2004), 459 – 484, DOI: 10.1016/j.amc.2003.08.130.
T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 3rd edition, The MIT Press, Cambridge, 1312 pages (2009), URL: https://mitpress.mit.edu/9780262533058/introduction-to-algorithms/.
R. W. Cottle, Manifestations of the Schur complement, Linear Algebra, and its Applications 8 (1974), 189 – 211, URL: http://aboutme.samexent.com/classes/fall08/ee8950/cottle.pdf.
B. Datta, Numerical Methods for Linear Control Systems, 1st edition, Academic Press, 640 pages (2003), URL: https://www.elsevier.com/books/numerical-methods-for-linear-control-systems/datta/978-0-12-203590-6.
J. Dongarra, V. Eijkhout and P. Luszczek, Recursive approach in sparse matrix LU factorization, Scientific Programming 9 (2001), 51 – 60, URL: https://icl.utk.edu/~luszczek/pubs/sciprog.pdf.
K. Georgiev and J. Wasniewski, Recursive version of LU decomposition, in: Numerical Analysis and Its Applications (NAA 2000), Lecture Notes in Computer Science, L. Vulkov, P. Yalamov and J. Wasniewski (editors), Vol. ´ 1988, Springer, Berlin — Heidelberg, DOI: 10.1007/3-540-45262-1_38.
D. Heller, A survey of parallel algorithms in numerical linear algebra, SIAM Review 20(4) (1978), 740 – 777, DOI: 10.1137/1020096.
A. J. Laub, Matrix Analysis for Scientists and Engineers, SIAM, Philadelphia, xiii + 157 pages (2004), URL: https://my.siam.org/Store/Product/viewproduct/?ProductId=991.
T. Lyche, Numerical Numerical Linear Algebra and Matrix Factorizations, 1st edition, Texts in Computational Science and Engineering series, Vol. 22, Springer, Switzerland, xxiii + 371 pages (2020), DOI: 10.1007/978-3-030-36468-7.
R. Mahfoudhi, A Fast Triangular Matrix Inversion, Proceedings of the World Congress on Engineering (WCE 2012), Vol. I (2012), July 4-6, 2012, London, UK (2012), URL: https://www.iaeng.org/publication/WCE2012/WCE2012_pp100-102.pdf.
M. G. Reuter and J. C. Hill, An efficient, block-by-block algorithm for inverting a block tridiagonal, nearly block Toeplitz matrix, Computational Science & Discovery 5(1) (2012), 014009, DOI: 10.1088/1749-4699/5/1/014009.
Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd edition, SIAM, xvii + 520 pages (2003), DOI: 10.1137/1.9780898718003.
B. Sousedík, R. G. Ghanem and E. T. Phipps, Hierarchical Schur complement preconditioner for the stochastic Galerkin finite element methods, Numerical Linear Algebra with Applications 21(1) (2013), 136 – 151, DOI: 10.1002/nla.1869.
C. F. Van Loan, The ubiquitous Kronecker product, Journal of Computational and Applied Mathematics 123(1-2) (2000), 85 – 100, DOI: 10.1016/S0377-0427(00)00393-9.
A. Yang, C. Liu, J. Chang and X. Guo, Research on parallel LU decomposition method and it’s application in circle transportation, Journal of Software 5(11) (2010), 1250 – 1255, DOI: 10.4304/jsw.5.11.1250-1255.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a CCAL that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
