Hierarchical matrices

Seminar Scientific Computing - Summer Term 2011

Linear algebra problems are basic problems which are part of almost all large scale computations, in particular, when they involve partial differential equations. Therefore, it is interesting to check what linear algebra tasks can be performed with linear complexity. The vector operations (vector sum x+y, scalar multiplication c*x, scalar product x, y ) are obvious candidates for linear complexity. However, whenever matrices are involved, the situation becomes worse. The operations Ax, A + B, A*B, inverse of A , etc. require O(N^ 2 ) or O(N3 ) operations. The O(N^ 2 )-case can be interpreted as linear complexity, since an N x N -matrix contains N2 data. However, it is unsatisfactory that one does not know whether a (general) linear system Ax = b (A regular) can be solved by an O(N2 )-algorithm. Usually, one is working with special subsets of matrices (diagonal, Toeplitz, tridiagonal etc.). For such matrices there exist already fast algorithms. But often one deals which more general matrices. The hierarchical matrix (H-matrix) technique is used to approximate the matrices which come from differential and integral equations. The storage requirement is O(N log N), complexity of the matrix-matrix multiplication and matrix inverse is O(Nlog2 N). You will study how to assembly such matrices and how to perform basic matrix operations. See more in www.hlib.org.

Contact