What is most efficient way to solve $A^{1/2} x = b$?

Question

Given $A$ a $n\times n$ real symmetric positive semidefinite matrix, $b$ a vector of dimension $n$. What is the most efficiently way to solve the linear system $$ A^{\frac12} x = b $$

I know the basic way which consists of doing an eigenvalue decomposition of $A$ first, and then take square-root of the diagonal matrix and finally solve the linear system. This basic way has a complexity of $O(n^3)$.

Is it possible to do better with any other practical implementations?

Answer 1

Common approaches to this problem include:

• Lanczos iteration
• Eigendecompsoition
• Cholesky/LDL factorization (depending on how you define $A^{1/2}$ or if $b$ is a spherically symmetric random vector)

Among these methods, Lanczos has the advantage of being "matrix free" and requiring very little storage. It is also iterative, and therefore allows you to trade time for accuracy. The downside is that the iteration must be run again if you have a new vector $b$. On the other hand, the factorization based approaches can be applied to many vectors efficiently after the factorization is computer.

Perhaps less common approaches include

• sketching A to get a low-rank approximation
• rational Krylov methods