STRUCTURE AND ALGORITHMS FOR RECURSIVELY LOW-RANK COMPRESSED MATRICES

A principled data structure is developed that enables the design of matrix algorithms by using tree traversals and that facilitates computer implementation, especially in the parallel setting, and three basic operations supported by the data structure—matrix-vector multiplication, matrix inversion, and determinant calculation—all of which have a strictly linear cost are presented.