I, and friends of mine, are interested in matrices which can be inverted / solved easily (i.e. in less than O(n^3)). I started to put together a github page dedicated to it and so far have identified:
- Diagonal Matrices
- Block Diagonal Matrices
- Low Rank Matrices
- Toeplitz Matrices
- Vandermonde Matrices
- Hierarchical Matrices (so far FMM and HODLR matrices)
I was hoping that any of you great people could suggest other special cases and ideally point to reading material on them. Hopefully this will be a useful resource for a number of people (e.g. researchers in math / engineering / physics etc.)
PS - The GitHub page is here: https://github.com/jkfitzsimons/Special_Matrices/blob/master/README.md
You should probably modify point (3) to low rank perturbations of full rank matrices.
Other special case are banded matrices and arrow head matrices. Tridiagonal matrices occur frequently in the solution of PDEs using alternating direction methods (ADI). Banded matrices are often used as preconditioners for more general sparse systems. Arrow head matrices are the result of domain decomposition techniques for large scale PDEs.
I would add general sparse matrices to your list and I recommend that you concentrate on how to solve the systems efficiently on a parallel machine.
I recommend that you study some of the the work done by the LAPACK, SCALAPACK, HSL (Harwell Subroutine Library), PARDISO, PSPIKE communities to name but a few. These names will easily lead you to the website, particularly if you include the search term "solver".
Currently, there is a lot of research focusing on how to solve linear systems efficiently in the face of the massive parallelism offered by emerging computer systems (the exascale projects). The main problem is to develop algorithms which are communication optimal, i.e. spend as little time as possible moving data through the memory hierarchy and between different processing units as these operations are far slower than floating point arithmetic.