A \(N\)-Body Solver for Square Root Iteration

Abstract

We develop the Sparse Approximate Matrix Multiply (\(\tt SpAMM\)) \(n\)-body solver for first order Newton Schulz iteration of the matrix square root and inverse square root. The solver performs recursive two-sided metric queries on a modified Cauchy-Schwarz criterion, culling negligible sub-volumes of the product-tensor for problems with structured decay in the sub-space metric. These sub-structures are shown to bound the relative error in the matrix-matrix product, and in favorable cases, to enjoy a reduced computational complexity governed by dimensionality reduction of the product volume. A main contribution is demonstration of a new, algebraic locality that develops under contractive identity iteration, with collapse of the metric-subspace onto the identity's plane diagonal, resulting in a stronger \(\tt SpAMM\) bound. Also, we carry out a first order {Fr\'{e}chet} analyses for single and dual channel instances of the square root iteration, and look at bifurcations due to ill-conditioning and a too aggressive \(\tt SpAMM\) approximation. Then, we show that extreme \(\tt SpAMM\) approximation and contractive identity iteration can be achieved for ill-conditioned systems through regularization, and we demonstrate the potential for acceleration with a scoping, product representation of the inverse factor.