Sparse matrix factorization in the implicit finite element method on petascale architecture

Significance Statement

Despite the potential of high performance computing in simulations and modeling in today’s technology, petascale computing platforms remain challenging for engineers and researchers to solve their problems on. Even matching a critical algorithm such as the sparse matrix factorization, central to many problems in science, engineering, and optimization, faces difficulty in adjusting to increasing computational power of high performance computing.

Dr. Seid Koric from the National Center for Supercomputing Applications at University of Illinois and Dr. Anshul Gupta from IBM T.J. Watson Research Center demonstrated that multifrontal sparse factorization algorithm with hybrid parallelization, such as one in the Watson Sparse Matrix Package (WSMP), can scale efficiently in todays’ large-scale supercomputers. The hardware used in these studies is the sustained petascale system of Blue Waters hosted at University of Illinois’ National Center for Supercomputing Applications. Blue Waters is considered one of the most powerful supercomputers in the world and is funded by the National Science Foundation (NSF) and the state of Illinois.  The challenging large sparse matrices used in this study with tens of millions of unknowns are from Dr. Koric’s multiphysics research with implicit finite element methods and often unsolvable by iterative solvers. The study is published in Computer Methods in Applied Mechanics and Engineering.

The general categories used in solving large sparse linear systems of equations are the direct methods and iterative methods. However, previous research has shown that direct methods provide faster solution than iterative methods for certain classes of linear systems, and they also possess sufficient scalability and robustness in tackling very large problem sizes of ill-conditioned finite element analysis equations on many thousands of processor cores.

The robust high-performance and easy-to-use software, Watson Sparse Matrix Package (WSMP), which Dr. Anshul Gupta was a lead author of, is frequently used for solving large sparse systems of linear equations. It has a unique feature in ability to exploit both shared-memory and distributed-memory parallelism using threads and message passing interface respectively. The multifrontal technique in Watson Sparse Matrix Package ensures that most floating point computation is performed by cache friendly level 2 and level 3 basic linear algebra subprograms.

Results from factorization time, parallel speedup and performance showed that 64 nodes is the minimum number of nodes that can fit the largest matrix case with 1 thread per node for the total of 64 threads (successfully solved in only 18 seconds). Watson Sparse Matrix Package was also found not to be bound  by memory access and interconnect communication bandwidths on Blue Waters. On smaller CPU thread counts, memory access time was drastically reduced by large amount of cache memory available, leading to extra speedup in addition to that from actual computation. Speedup nevertheless remained high for large problems reaching 13,179 and 76.4 TFlops at the largest of thread count of 65,536 used in this study.

When full scale evaluation were performed using direct multifrontal factorization method with a hybrid parallel implementation in WSMP, it performed exceedingly well on a petascale high-performance computing system of Blue Waters, and delivered excellent factorization robustly with high scalability. Indeed, more than 40 million equations solved on more than 65,000 of cores with 76.4 TFlops of sustained performance.

It is believed that the unprecedented level of parallel scalability and robustness of the direct solver in implicit finite element method, demonstrated for the first time by Drs. Koric and Gupta on the sustained peta-scale system of Blue Waters, will lead to a massive leap in terms of advances in high-fidelity modeling and design in science and engineering 


Sparse matrix factorization in the implicit finite element method on petascale architecture. Advances in Engineering

Sparse matrix factorization in the implicit finite element method on petascale architecture. Advances in Engineering

About the author


Technical Program Manager, National Center for Supercomputing Applications -NCSA

Research Associate Professor, Mechanical Science and Engineering – MechSE , University of Illinois

Seid Koric has more than 19 years of experience at the National Center for Supercomputing Applications (NCSA), conducting cutting-edge applied research and providing consulting for the national academic and industrial computational communities on the center’s high-performance computing (HPC) platforms. He earned M.S. in aerospace engineering (1999) and Ph.D. in mechanical engineering (2006) from the University of Illinois at Urbana-Champaign. Dr.  Koric is currently the technical program manager for the NCSA Industry – the largest industrial HPC outreach in the world.

Dr. Koric is leading several research projects on the NCSA’s peta-scale high performance computing system of Blue Waters that aim to demonstrate the scalability of engineering industrial applications on the peta and even potentially exa-scale computing level. He has achieved a few new world records in parallel scaling with both commercial and academic finite element codes in 2014 and 2015. He is one of the most prolific researchers on Blue Waters with 27 to date published research publications and earning many prestigious high performance computing awards.

He also serves as Research Professor in the Mechanical Science and Engineering Department at the University of Illinois, Urbana-Champaign. His research interests are in multiphysics modeling of complex engineering processes and extreme scale high performance computing in science and engineering. Dr. Koric is also actively working in the areas of material processing, advanced digital manufacturing, bio-mechanics, and fractal mechanics. He has published or contributed to over 50 research papers and articles on a diverse range of topics.

About the author


Principal Research Staff Member, Mathematical Sciences, IBM T.J. Watson Research Center   

Anshul Gupta is a Principal Research Staff Member in the Mathematical Science Department at IBM T.J. Watson Research Center in Yorktown Heights, New York.  His research interests include sparse matrix computations and their applications in optimization and computational sciences, parallel algorithms, and graph/combinatorial algorithms for scientific computing. He has coauthored several journal articles and conference papers on these topics and a textbook titled “Introduction to Parallel Computing.”

He is the primary author of Watson Sparse Matrix Package (WSMP), one of the most robust and scalable parallel direct solvers for large sparse systems of linear equations.

Dr. Gupta received a B.Tech. degree from the Indian Institute of Technology, New Delhi, in 1988 and a Ph.D. in 1995 from the University of Minnesota, both in Computer Science.

Journal Reference

Seid Koric1,2, Anshul Gupta3. Sparse matrix factorization in the implicit finite element method on petascale architectureComputer Methods in Applied Mechanics and Engineering, Volume 302, 2016, Pages 281–292.

[expand title=”Show Affiliations”]
  1. National Center for Supercomputing Applications, University of Illinois at Urbana-Champaign, USA
  2. Department of Mechanical Science and Engineering, University of Illinois at Urbana-Champaign, USA
  3. Mathematical Sciences, IBM T.J. Watson Research Center, USA



Go To Computer Methods in Applied Mechanics and Engineering





Check Also

Vortex evolution in a rotating tank with an off-axis drain - Advances in Engineering

Vortex evolution in a rotating tank with an off-axis drain