Recompression techniques for adaptive cross approximation (Q732338)

The adaptive cross approximation method (ACA) generates low-rank approximations to suitable \(m\times n\) sub-blocks of discrete integral formulations of elliptic boundary value problems. The discretization method by which the sub-blocks are obtained from the integral operator is either the Nyström, the collocation or the Galerkin method. ACA requires \(k(m+n)\), \(k\sim|\log \varepsilon|\) (\(\varepsilon \) represents the approximation accuracy) units of storage and is generated in a purely algebraic manner using only few of matrix entries. Also it is an adaptive algorithm, i.e. the rank of approximation is determined during the approximation. The authors present recompression techniques based on optimized singular value decomposition, Chebyshev approximation and discrete cosine transform. The required amount of storage is brought down to sublinear order \(kk'\), where \(k'\) depends logarithmically on \(\varepsilon \) but is independent of the matrix size. Numerical results support the derived estimates.