Skip to main content
SpringerLink
Log in

A Left-Looking Sparse Cholesky Parallel Algorithm for Shared Memory Multiprocessors

  • Conference paper
  • First Online:
Advances in Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD 2021)

Part of the book series: Lecture Notes on Data Engineering and Communications Technologies ((LNDECT,volume 89))

  • 1999 Accesses

Abstract

Sparse Cholesky factorization is the core algorithm for solving large-scale sparse linear equations, and is the most time-consuming step in the solution process. In this paper, a left-looking sparse Cholesky factorization parallel algorithm is proposed, and a thread pool mechanism is introduced, which is suitable for shared memory MIMD multiprocessors. Experimental results: The effectiveness of the proposed algorithm was verified by comparing it with the SuiteSparse library.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 219.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 279.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Amestoy, P.R., Davis, T.A., Duff, I.S.: An approximate minimum degree ordering algorithm. SIAM J. Matrix Anal. Appl. 17(4), 886–905 (1996)

    Article  MathSciNet  Google Scholar 

  2. Davis, T.A., et al.: A column approximate minimum degree ordering algorithm. ACM Trans. Math. Softw. (TOMS) 30(3), 353–376 (2004)

    Article  MathSciNet  Google Scholar 

  3. Karypis, G., Kumar, V.: METIS–unstructured graph partitioning and sparse matrix ordering system, version 2.0 (1995)

    Google Scholar 

  4. Duff, I.S., Reid, J.K.: The multifrontal solution of indefinite sparse symmetric linear. ACM Trans. Math. Softw. (TOMS) 9(3), 302–325 (1983)

    Article  MathSciNet  Google Scholar 

  5. Duff, I.S., Reid, J.K.: The multifrontal solution of unsymmetric sets of linear equations. SIAM J. Sci. Stat. Comput. 5(3), 633–641 (1984)

    Article  MathSciNet  Google Scholar 

  6. Duff, I.S.: Parallel implementation of multifrontal schemes. Parallel Comput. 3(3), 193–204 (1986)

    Article  MathSciNet  Google Scholar 

  7. Liu, J.W.H.: The multifrontal method for sparse matrix solution: theory and practice. SIAM Rev. 34(1), 82–109 (1992)

    Article  MathSciNet  Google Scholar 

  8. Davis, T.A., Duff, I.S.: A combined unifrontal/multifrontal method for unsymmetric sparse matrices. ACM Trans. Math. Softw. (TOMS) 25(1), 1–20 (1999)

    Article  MathSciNet  Google Scholar 

  9. Amestoy, P.R., Duff, I.S., L’excellent, J.-Y.: Multifrontal parallel distributed symmetric and unsymmetric solvers. Comput. Meth. Appl. Mech. Eng. 184(2–4), 501–520 (2000)

    Article  Google Scholar 

  10. Xia, J.: Efficient structured multifrontal factorization for general large sparse matrices. SIAM J. Sci. Comput. 35(2), A832–A860 (2013)

    Article  MathSciNet  Google Scholar 

  11. Rothberg, E., Gupta, A.: Efficient sparse matrix factorization on high performance workstations-exploiting the memory hierarchy. ACM Trans. Math. Softw. (TOMS) 17(3), 313–334 (1991)

    Article  Google Scholar 

  12. Ng, E., Peyton, B.W.: A supernodal Cholesky factorization algorithm for shared-memory multiprocessors. SIAM J. Sci. Comput. 14(4), 761–769 (1993)

    Article  MathSciNet  Google Scholar 

  13. Ng, E.G., Peyton, B.W.: Block sparse Cholesky algorithms on advanced uniprocessor computers. SIAM J. Sci. Comput. 14(5), 1034–1056 (1993)

    Article  MathSciNet  Google Scholar 

  14. Ashcraft, C., Grimes, R.G.: SPOOLES: an object-oriented sparse matrix library. In: PPSC (1999)

    Google Scholar 

  15. Dobrian, F., Kumfert, G., Pothen, A.: The design of sparse direct solvers using object-oriented techniques. In: Langtangen, H.P., Bruaset, A.M., Quak, E. (eds.) Advances in Software Tools for Scientific Computing, pp. 89–131. Springer, Heidelberg (2000). https://doi.org/10.1007/978-3-642-57172-5_3

  16. Rotkin, V., Toledo, S.: The design and implementation of a new out-of-core sparse Cholesky factorization method. ACM Trans. Math. Softw. (TOMS) 30(1), 19–46 (2004)

    Article  MathSciNet  Google Scholar 

  17. Chen, Y., et al.: Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate. ACM Trans. Math. Softw. (TOMS) 35(3), 1–14 (2008)

    Article  MathSciNet  Google Scholar 

  18. Ashcraft, C., Grimes, R.: The influence of relaxed supernode partitions on the multifrontal method. ACM Trans. Math. Softw. 15(4), 291–309 (1989)

    Article  Google Scholar 

  19. Davis, T.A., Yifan, H.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw. (TOMS) 38(1), 1–25 (2011)

    MathSciNet  MATH  Google Scholar 

  20. Liu, J.W.H.: The role of elimination trees in sparse factorization. SIAM J. Matrix Anal. Appl. 11(1), 134–172 (1990)

    Article  MathSciNet  Google Scholar 

  21. Dongarra, J.J., et al.: A set of level 3 basic linear algebra subprograms. ACM Trans. Math. Softw. (TOMS) 16(1), 1–17 (1990)

    Article  MathSciNet  Google Scholar 

  22. Anderson, E., et al.: LAPACK Users’ Guide. Society for Industrial and Applied Mathematics (1999)

    Google Scholar 

  23. Rennich, S.C., Stosic, D., Davis, T.A.: Accelerating sparse Cholesky factorization on GPUs. Parallel Comput. 59, 140–150 (2016)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgments

The research was partially funded by the National Key R&D Program of China (Grant Nos. 2018YFB0204302), the Key Program of National Natural Science Foundation of China (Grant No. 92055213), and the National Natural Science Foundation of China (Grant Nos. 61872127 and 61751204).

Author information

Authors and Affiliations

  1. College of Information Science and Engineering, Hunan University, Changsha, 410082, Hunan, China

    Minlu Dai, Wangdong Yang, Qinyun Cai, Junsheng Zhou, Keqin Li & Kenli Li

  2. The National Supercomputing Center in Changsha, Changsha, 410082, Hunan, China

    Minlu Dai, Wangdong Yang, Qinyun Cai, Junsheng Zhou, Keqin Li & Kenli Li

Authors
  1. Minlu Dai
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wangdong Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Qinyun Cai
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Junsheng Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Keqin Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Kenli Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wangdong Yang .

Editor information

Editors and Affiliations

  1. Guizhou University, Guiyang, China

    Quan Xie

  2. Computer Science and Mathematics, University of São Paulo (USP), Ribeirão Preto, São Paulo, Brazil

    Liang Zhao

  3. College of Electrical and Information, Hunan University, Changsha, China

    Kenli Li

  4. Department of Mathematics, NIT Jalandhar, Jalandhar, India

    Anupam Yadav

  5. Electrical and Electronic Engineering, Nanyang Technological University, Singapore, Singapore

    Lipo Wang

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Dai, M., Yang, W., Cai, Q., Zhou, J., Li, K., Li, K. (2022). A Left-Looking Sparse Cholesky Parallel Algorithm for Shared Memory Multiprocessors. In: Xie, Q., Zhao, L., Li, K., Yadav, A., Wang, L. (eds) Advances in Natural Computation, Fuzzy Systems and Knowledge Discovery. ICNC-FSKD 2021. Lecture Notes on Data Engineering and Communications Technologies, vol 89. Springer, Cham. https://doi.org/10.1007/978-3-030-89698-0_21

Download citation

Publish with us

Policies and ethics

Search

Navigation