Sparse Matrix Factorization Using Multifrontal QR and Supernodal Cholesky Methods
DOI:
https://doi.org/10.25077/jmua.15.3.449-459.2026Keywords:
Factorization, Ordering, Multifrontal QR, Supernodal Cholesky, Sparsity SlopeAbstract
This paper discusses the factorization of sparse matrices. A nested dissection method is used to reorder sparse matrices, while multifrontal QR and supernodal Cholesky methods are applied to factorize them. Simulations were carried out on three groups of matrices of the same size, with each group consisting of four matrices of varying sparsities. The objectives of this study are to investigate the effect of sparsity and the performance of the factorization methods. Results show that the effects of sparsity on the parameters of the matrix groups depend on their sparsity slope. Ultimately, it is demonstrated that supernodal Cholesky factorization achieves better performance than multifrontal QR.
References
Patrick Amestoy et al. “On the Complexity of the Block Low-Rank Multifrontal Factorizationâ€. In: SIAM Journal on Scientific Computing 39 (4 Jan. 2017), A1710–A1740. issn: 1064-8275. doi:10.1137/16M1077192.
Yonghong Zhang, Peijia Zheng, and Weiqi Luo. “Privacy-Preserving Outsourcing Computation of QR Decomposition in the Encrypted Domainâ€. In: 2019 18th IEEE International Conference On Trust, Security And Privacy In Computing And Communications/13th IEEE International Conference On Big Data Science And Engineering (TrustCom/BigDataSE). IEEE, Aug. 2019, pp. 389–396. isbn: 978-1-7281-2777-4. doi: 10.1109/TrustCom/BigDataSE.2019.00059.
Lingzan Yu et al. “Efficient Noninteractive Outsourcing of Large-Scale QR and LU Factorizationsâ€. In: Security and Communication Networks 2021 (June 2021), pp. 1–14. issn: 1939-0122. doi:10.1155/2021/6184920.
I. S. Duff and J. K. Reid. “The Multifrontal Solution of Indefinite Sparse Symmetric Linearâ€. In: ACM Transactions on Mathematical Software 9 (3 Sept. 1983), pp. 302–325. issn: 0098-3500. doi:10.1145/356044.356047.
Emmanuel Agullo et al. “Multifrontal QR Factorization for Multicore Architectures over Runtime Systemsâ€. In: 2013, pp. 521–532. doi:10.1007/978-3-642-40047-6_53.
Sencer Nuri Yeralan et al. “Algorithm 980â€. In: ACM Transactions on Mathematical Software 44 (2 June 2018), pp. 1–29. issn: 0098-3500. doi: 10.1145/3065870.
Gustavo M. Hebling et al. “Sparse and numerically stable implementation of a distribution system state estimation based on Multifrontal QR factorizationâ€. In: Electric Power Systems Research 189 (Dec. 2020), p. 106734. issn:03787796. doi:10.1016/j.epsr.2020.106734.
Meng Tang, Mohamed Gadou, and Sanjay Ranka. “A Multithreaded Algorithm for Sparse Cholesky Factorization on Hybrid Multicore Architecturesâ€. In: Procedia Computer Science 108 (2017), pp. 616–625. issn: 18770509. doi:10.1016/j.procs.2017.05.260.
Azzam Haidar et al. “RETRACTED: Batched matrix computations on hardware accelerators based on GPUsâ€. In: The International Journal of High Performance Computing Applications 29 (2 May 2015), pp. 193–208. issn:1094-3420. doi: 10.1177/1094342014567546.
Dan Zou et al. “Supernodal sparse Cholesky factorization on graphics processing unitsâ€. In: Concurrency and Computation: Practice and Experience 26 (16 Nov. 2014), pp. 2713–2726. issn:1532-0626. doi: 10.1002/cpe.3158.
Steven C. Rennich, Darko Stosic, and Timothy A. Davis. “Accelerating sparse Cholesky factorization on GPUsâ€. In: Parallel Computing 59 (Nov. 2016), pp. 140–150. issn: 01678191. doi:10.1016/j.parco.2016.06.004.
Yichun Sun, Hengzhu Liu, and Tong Zhou. “Sparse Cholesky Factorization on FPGA Using Parameterized Modelâ€. In: Mathematical Problems in Engineering 2017 (1 Jan. 2017). issn: 1024-123X. doi:10.1155/2017/3021591.
Erik G. Boman and Michael M. Wolf. “A nested dissection partitioning method for parallel sparse matrix-vector multiplicationâ€. In: 2013 IEEE High Performance Extreme Computing Conference (HPEC). IEEE, Sept. 2013, pp. 1–6. isbn: 978-1-4799-1365-7. doi:10.1109/HPEC.2013.6670333.
Scott Kolodziej et al. “The SuiteSparse Matrix Collection Website Interfaceâ€. In: Journal of Open Source Software 4 (35 Mar. 2019), p. 1244. issn: 2475-9066. doi: 10.21105/joss.01244.
Timothy A. Davis. “Algorithm 1000â€. In: ACM Transactions on Mathematical Software 45 (4 Dec. 2019), pp. 1–25. issn: 0098-3500. doi: 10.1145/3322125.
Timothy A. Davis. Direct Methods for Sparse Linear Systems. Society for Industrial and Applied Mathematics, Jan. 2006. isbn: 978-0-89871-613-9. doi:10.1137/1.9780898718881.
I. S. Duff, A. M. Erisman, and J. K. Reid. Direct Methods for Sparse Matrices. Oxford University PressOxford, Jan. 2017. isbn:0198508387. doi:10.1093/acprof:oso/9780198508380.001.0001.
David Padua. Encyclopedia of Parallel Computing. Ed. by David Padua. Springer US, 2011. isbn: 978-0-387-09765-7. doi:10.1007/978-0-387-09766-4.
Austin R. Benson, David F. Gleich, and James Demmel. “Direct QR factorizations for tall-and-skinny matrices in MapReduce architecturesâ€. In: 2013 IEEE International Conference on Big Data. IEEE, Oct. 2013, pp. 264–272. isbn: 978-1-4799-1293-3. doi:10.1109/BigData.2013.6691583.
G.R. Lindfield and J.E.T. Penny. Numerical Methods Using MATLAB. 4th ed. Elsevier, 2019.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Departemen Matematika dan Sains Data FMIPA UNAND
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
All articles published in Jurnal Matematika UNAND (JMUA) are open access and licensed under the Creative Commons Attribution-ShareAlike (CC BY-SA) license. This ensures that the content is freely available to all users and can be shared and adapted, provided appropriate credit is given and any adaptations are distributed under the same license.
Copyright Holder
The copyright of all articles published in Jurnal Matematika UNAND is held by the Departemen Matematika dan Sains Data, Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA), Universitas Andalas (UNAND). This applies to all published versions, including the HTML and PDF formats of the articles.
Author Rights
While the Departemen Matematika dan Sains Data FMIPA UNAND holds the copyright for all published content, authors retain important rights under the Creative Commons Attribution-ShareAlike 4.0 International License (CC BY-SA). This license grants authors and users the following rights:
- Reuse: Authors can reuse and distribute their work for any lawful purpose, including sharing on personal websites, institutional repositories, or in subsequent publications.
- Attribution and Adaptation: Authors and others may remix, adapt, and build upon the published work for any purpose, even commercially, as long as proper credit is given to the original authors, and any derivative works are distributed under the same CC BY-SA license.
Creative Commons License (CC BY-SA)
Under the terms of the CC BY-SA license, users are free to:
- Share: Copy and redistribute the material in any medium or format.
- Adapt: Remix, transform, and build upon the material for any purpose, even commercially.
However, the following conditions apply:
- Attribution: Users must give appropriate credit to the original author(s) and Departemen Matematika dan Sains Data FMIPA UNAND, provide a link to the license, and indicate if changes were made. Attribution must not imply endorsement by the author or the journal.
- ShareAlike: If users remix, transform, or build upon the material, they must distribute their contributions under the same license as the original.
For more information about the CC BY-SA license, please visit the Creative Commons website.
Third-Party Content
If authors include third-party material (such as figures, tables, or images) that is not covered by a Creative Commons license, they must obtain the necessary permissions for reuse and provide proper attribution. Authors are required to ensure that any third-party content complies with open-access licensing requirements or includes permissions for redistribution under similar terms.
Copyright and Licensing Information Display
The copyright and licensing terms will be clearly displayed on each article's landing page, as well as within the full-text versions (HTML and PDF) of all published articles.
No "All Rights Reserved"
As an open-access journal, JMUA does not use "All Rights Reserved" policies. Instead, the CC BY-SA license ensures that the works remain accessible and reusable for a wide audience while still protecting both the authors' and the copyright holder's rights.
Â
