Excluded sums and quasiseparable matrices.

The idea of Edelman et al. (published in 2005 in SIAM News) for fast evaluation of excluded sums and their relation with the non-recursive multipole method was largely unnoticed. The authors promised to give a new implementation of the multipole method based on their (quite elegant) approach however up to now nothing is known. From my point of view the problem is that they didn’t succeed with the efficient implementation of functional approximations. In our new paper this idea is fully investigated in the one-dimensional case. It appears that it can be done in a simple manner by using successive low-rank skeleton approximation of a matrices in the lower triangular part and in the upper triangular part of the matrix and it can be shown that the obtained method works for an arbitrary quasiseparable matrix (i.e., matrix where every submatrix strictly below or over the diagonal has low rank), and moreover, a new representation for the class of quasiseparable matrices is obtained. This is a first step in the project “Matrix methods for the N-body problems”.

The future research will go in two directions. The first one concerns quasiseparable matrices and effective solvers and eigensolvers using the new representation and the second is the generalization to two or three dimensions.