Sparse algebra algorithms and high performance implementation

Brief overview

Sparse algebra is an important field of computational science with a huge number of scientific and engineering applications from various problem domains. Our group works on the development of parallel algorithms and software for a numerical solution of large sparse systems of linear algebraic equations (SLAE) – a critical and time consuming part of many computational processes. Our direct solver is capable of solving sparse systems with a symmetric positive definite matrix and optimized for shared memory systems.

Team

  • Iosif Meyerov, PhD, associate professor, Software Department, UNN (project leader)
  • Alexander Sysoyev, PhD,assistant professor, Software Department, UNN
  • Evgeny Kozinov, assistant professor, Software Department, UNN
  • Anna Pirova, post-graduate student, Software Department, UNN
  • Sergey Lebedev, master student, Software Department, UNN
  • Sophia Klyan, master student, Software Department, UNN
  • Svetlana Nosova, post-graduate student, Software Department, UNN
  • Sergey Ryzhov, master student, Informatics and Computer-aided design Department, UNN
  • Yana Shulgina, student, Software Department, UNN
  • Stanislav Filippenko, master student, Software Department, UNN
  • DmitryAhmedzhanov, student, UNN
  • Xenia Baykova, student, UNN
  • Dmitry Gorokhov, student, Software Department, UNN
  • Nikita Kudryavtsev, student, Software Department, UNN
  • Ilya Lebedev, software engineer, Software Department, UNN

We are grateful to our colleagues Yu. Bartenev, S. Bastrakov, V. Gergel, A. Linev, G. Osipov, M. Prilutsky, N. Starostin for useful discussions and attention to our work.

Main results

  1. We develop a new direct solver for sparse linear systems of equations with symmetric positive definite matrices. The solver is based on classical multifrontal method with a number of modifications mainly oriented to parallel work in shared memory systems. The software will be publically available soon.
  2. We develop a new modification of multilevel nested dissection scheme of sparse matrix reordering to minimize a fill-in during factorization phase. The scheme is implemented in “MORSy” and is competitive to the state of the art libraries on the quality and performance. The software is publically available and can be downloaded.
  3. Our algorithms are used in the “Virtual heart” – cardiac activity simulation software developed in UNN.

Current research

Our research is mainly focused on sparse SLAE direct solution methods investigation and its high performance implementation.
Now we work in the following directions:

  • Algorithms and software for sparse matrix reordering. Quality improvement of the algorithms and parallelization for shared memory systems.
  • Algorithms and software for sparse SLAE direct solution. Performance improvement and parallelization for shared memory systems. Investigation of opportunities of porting software to accelerators (GPU, Xeon Phi).

Selected papers

  • Pirova A., Meyerov I., Kozinov E., Lebedev S. PMORSy: parallel sparse matrix ordering software for fill-in minimization // Optimization Methods and Software. -Vol. 32, No. 2. – 2017. – P. 274 -289. DOI: http://dx.doi.org/10.1080/10556788.2016.1193177
  • Lebedev S., Akhmedzhanov D., Kozinov E., Meyerov I., Pirova A., Sysoyev A. Dynamic Parallelization Strategies for Multifrontal Sparse Cholesky Factorization // Parallel Computing Technologies. – Springer International Publishing, 2015. – P. 68-79.
  • Pirova A., Meyerov I.  MORSy – a new tool for sparse matrix reordering // An International Conference on Engineering and Applied Sciences Optimization. M. Papadrakakis, M.G. Karlaftis, N.D. Lagaros (eds.) (Kos Island, Greece, 4-6 June 2014). – pp. 1952-1963.
  • Bastrakov S. , Meyerov I., Gergel V., Gonoskov A., Gorshkov A., Efimenko E., Ivanchenko M., Kirillin M., Malova A., Osipov G.,  Petrov V., Surmin I., Vildemanov A. High performance computing in biomedical applications // Procedia Computer Science.  Volume 18. –Elsevier B.V., 2013. – Pp. 10–19.
  • Gergel V., BarkalovK., Meyerov I., Sysoyev A. et al. Parallel Computing. Technologies and numerical methods, N. Novgorod, UNN Press, 2013. (In Russian)

Achievements, projects and grants

The study was partially supported by the RFBR, research project No. 14-01-3145514.

Additional info

MORSy – sparse Matrix ORdering Software for fill-in minimization