Computational PDEs

Implementation of sparse matrix multiplications in NGSolve

Project plan

In this project the student(s) shall implement and extend the functionality of matrix multiplications in NGSolve. NGSolve is written in C++ and has a rich python interface. The most part of this project addresses the C++-level of the software.

For this project there are two relevant formats for sparse matrices involved:

  • The compressed row storage format which is a general purpose sparse matrix format and
  • an element-by-element matrix which is a special type of block (diagonal) matrix.

In this project the matrix-matrix multiplication between matrices of these types shall be investigated and implemented.

An important part of the project consists of gaining the understanding of the already implemented matrix classes and a proper reporting of it.

  1. Install NGSolve from source (C++, cmake, ...)
  2. "Discover" sparse matrix format (python-level) in NGSolve, e.g. by running
    • NGSolve-source/py_tutorials/poisson.py and inspecting a.mat
    • NGSolve-source/tests/pytest/test_matrix.py::test_sparsematrix_access
  3. Learn about the compressed row storage format, e.g. from https://de.wikipedia.org/wiki/Compressed_Row_Storage
  4. Discover sparse matrix format (C++-level) in NGSolve from
    • NGSolve-source/linalg/sparsematrix.cpp
    • NGSolve-source/linalg/basematrix.{h,c}pp
    • NGSolve-source/linalg/sparsematrix_impl.hpp
  5. Discover element-by-element matrix format (C++-level) in NGSolve from
    • NGSolve-source/linalg/elementbyelement.{h,c}pp
  6. Write a short sparsematrix * sparsematrix test example (from python, use small dimensions!)
  7. Discover how matrix multiplications for sparse matrices are implemented. See:
    • NGSolve-source/linalg/python_linalg.cpp, keyword__matmul__
  8. Learn about the implementation of MatMult in NGSolve-source/linalg/sparsematrix.cpp
  9. Write a conversion from element-by-element matrices to sparse matrices as a member fct. of an element-by-element-matrix (realized from within ngstrefftz (find it on github, ask Paul Stocker or Christoph Lehrenfeld ): a. Expose EBE matrix to python b. Add conversion to sparse-matrix as a member function
  10. Write a specification of the matrix mult for sparse-matrix times EBE matrix (and vice versa)
  11. Test and document it.

The project shall result in a repository that holds its own fork of a git repository of NGSolve as a submodule. In this repository should be:

  • documentation of the underlying (existing) data formats and classes
  • documentation of the projects progress,
  • examples/test (that are not supposed to end up in the NGSolve repo)
  • test suite for additional tests
  • continuous integration facilities including an automatic evaluation of a (gitlab CI / github actions)

If you are interested in the project, contact C. Lehrenfeld and/or P. Stocker and more information will be provided.