Is there a way to solve an underdetermined linear system $Ax=b$ using the Fast Multipole Method? I have an underdetermined linear system $Ax=b$. We may assume $A$ is full rank. The entries in $A$ satisfy the conditions for the Fast Multipole Method (FMM) to be applied, i.e. the matrix-vector product $Ay$ can be computed very quickly.
Is it possible to make use of the FMM to accelerate the solving of this equation? Is there any existing algorithm based on FMM for this?
Some remarks:

*

*The size $(m,n)$ of $A$ is very larger, in my current settings, $m\sim10000,\ n\sim100000$.


*Since the system is underdetermined, I hope the solution is the one that minimizes $\|x\|_2$.


*The main difficulty seems to be writing the equation in an iterative form.
 A: The minimum norm solution satisfies the normal equations $x = A^\top (AA^\top)^{-1}b$. If both the matrix-vector product $y \mapsto Ay$ and the matrix-transpose-vector product $y \mapsto A^\top y$ can be computed quickly, then $AA^\top y = b$ is a system of linear equations with a positive definite matrix and can be solved by the conjugate gradient method. The product $y \mapsto AA^\top y$ can be computed by composing the fast matrix-transpose-vector and matrix-vector products and is thus fast. Thus, you can compute $y = (AA^\top)^{-1}b$ using conjugate gradient and $x = A^\top y$ using the fast matrix-tranpose-vector product.
The conjugate gradient approach is only advised on speed and accuracy grounds if the matrix $A$ is well-conditioned in the sense that $\kappa(A) := \sigma_{\rm max}(A) / \sigma_{\rm min}(A)$ is modestly sized. The condition number of $AA^\top$ is the square of the condition number of $A$: $\kappa(AA^\top) = (\kappa(A))^2$. If the condition number of $AA^\top$ is large, the conjugate gradient method will take many iterations. If you can devise an effective preconditioner, this may help accelerate your method.
One might hope for a direct method which need not have an iteration count depending on the conditioning of $A$. I do not believe such an algorithm is known if fast multiplications by $A$ are computed by the fast multipole method. However, there are a variety of other FMM-related ways of representing and computing with a matrix $A$ with rank structure which may be worth investigating. This is a very broad and active field with many competing methods championed by different researchers. One possible low-rank structure to look into is the HSS matrix structure. If your matrix $A$ has not just FMM but HSS structure, I believe it's almost certain the $ULV$ factorization approach of Xi and coauthors can be adapted to the minimum-norm case (the original algorithm is in the least-squares context).
