Sparse Matrix Factorization Using Multifrontal QR and Supernodal Cholesky Methods

Authors

DOI:

https://doi.org/10.25077/jmua.15.3.449-459.2026

Keywords:

Factorization, Ordering, Multifrontal QR, Supernodal Cholesky, Sparsity Slope

Abstract

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.

Downloads

Download data is not yet available.

Author Biographies

Moh Hasan, Universitas Jember

Moh Hasan is a lecturer (Lektor Kepala) at the University of Jember. He received a PhD degree in Mathematical and Statistical Modeling from University of Wageningen, Netherland. He is interested in matrix computation (including graph problems) and modeling of dynamical systems.

Chintya Monikasari, Universitas Jember

Chintya Monikasari is a student at Universitas Jember. She received a sarjana degree in mathematics from Universitas Jember, Indonesia. She is interested in matrix computation.

Kusbudiono, Universitas Jember

Kusbudiono is a lecturer (Lektor) at University of Jember. He received a master degree in mathematics from ITS, Indonesia. He is interested in applied mathematics, graph theory, and matrix computation.

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

31-07-2026

How to Cite

Hasan, M., Monikasari, C., & Kusbudiono. (2026). Sparse Matrix Factorization Using Multifrontal QR and Supernodal Cholesky Methods. Jurnal Matematika UNAND, 15(3), 449–459. https://doi.org/10.25077/jmua.15.3.449-459.2026

Issue

Vol. 15 No. 3 (2026)

Section

Articles

License

Copyright (c) 2026 Departemen Matematika dan Sains Data FMIPA UNAND

Creative Commons License

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 4.0 International License (CC BY-SA 4.0). This license allows published content to be freely accessed, shared, redistributed, and adapted for any purpose, including commercial use, provided that the applicable license conditions are followed.

Copyright Holder

The copyright of 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), in accordance with the journal's stated copyright policy.

Author Rights

Under the CC BY-SA 4.0 license, authors may share, distribute, and reuse their published articles, subject to the applicable license conditions. These rights include:

  • Self-Archiving: Authors may deposit their published articles in institutional repositories, personal websites, or academic platforms.

  • Reuse: Authors may reuse their published work in subsequent publications, research, teaching materials, or other lawful purposes, provided that appropriate attribution is maintained.

  • Distribution: Authors may share and distribute their published articles without requiring additional permission under the terms of the license.

Creative Commons License (CC BY-SA 4.0)

Under the CC BY-SA 4.0 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, including commercial purposes.

These permissions are subject to the following conditions:

  • Attribution: Users must give appropriate credit to the original author(s), retain relevant copyright notices, provide a link to the license, and indicate if changes were made. Attribution must not imply endorsement by the author(s), copyright holder, or journal.

  • ShareAlike: If users remix, transform, or build upon the material, they must distribute their contributions under the same CC BY-SA 4.0 license or a compatible license.

  • No Additional Restrictions: Users may not apply legal terms or technological measures that legally restrict others from exercising the rights granted by the license.

For more information about the CC BY-SA 4.0 license, please visit:

https://creativecommons.org/licenses/by-sa/4.0/

Third-Party Content

Third-party materials, including figures, tables, photographs, and illustrations, are covered by the article's CC BY-SA 4.0 license only when their inclusion under that license is authorized.

Materials excluded from the license must be clearly identified with appropriate copyright notices and attribution. Authors are responsible for obtaining any necessary permissions, while users must comply with the applicable licensing terms or permissions when reusing excluded materials.

Copyright and Licensing Information

Copyright and licensing information should be clearly displayed on each published article's landing page and included in the full-text versions (HTML and PDF), where applicable, to ensure transparency regarding copyright ownership and permitted reuse.