A N-Body Solver for Square Root Iteration
From MaRDI portal
Publication:6264808
Abstract: We develop the Sparse Approximate Matrix Multiply () -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 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 approximation. Then, we show that extreme 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.
This page was built for publication: A $N$-Body Solver for Square Root Iteration
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6264808)
