Foundations of Computational Mathematics, Workshop on Numerical Linear Algebra location:Hong Kong date:20-22 June 2008
Sparse matrices are an important tool for solving numerical problems in a fast computational manner by exploiting the efficiency connected to operations involving zeros. Matrices having too few zeros are called dense. Dense however does not mean unstructured. Quite often structure is hidden inside the matrix. A structured rank matrix is such a dense matrix having submatrices of low rank. Even though these elements are not zero, efficient algorithms can be built exploiting the low rank properties of this matrix. We will illustrate this by an example. It will be shown how the definite tridiagonal symmetric generalized eigenproblem transforms into computing the eigenvalues of a dense structured rank matrix. Exploiting this structure reduces the overhead due to computing with dense matrices, by a factor n (with n the matrix size).