# Which dense matrices are hard to invert?

Suppose I'm solving $$Ax=b$$ for dense $$m\times d$$ matrix $$A$$. For which $$A$$ is this hard to do?

More concretely, is there any work on estimating the error after $$k$$ steps of iterative solver, $$k\le d$$, for some specific solvers, based on properties of $$A$$? For random isotropic vector $$x$$ and large $$d$$, a useful property proved here is that

$$T^k x \approx c \operatorname{Tr}(T^k)$$

Hence this comes down to understanding how fast $$\operatorname{Tr}(T^k)$$ decays where $$T$$ is the iteration matrix of corresponding solver. Which properties of $$A$$ result in $$\operatorname{Tr}(T^d)$$ being large?

Classical approach formulates difficulty in terms of condition number $$\kappa(A)$$, but this comes into play after many steps, ie $$k>d^2$$. When $$d$$ is huge, we can only afford $$k=O(d)$$ steps. For instance, modern language model might have $$d\approx$$10B and be trained for 1B steps. A linear analogue of this problem is to solve $$Ax=b$$ where $$A$$ is a dense $$10B\times200B$$ matrix, in less time than it takes to read the matrix $$A$$.

For "single step gradient descent", you can show that an expression involving second/third moments of the matrix determine the difficulty of approximate inversion for gradient descent using $$k=1$$, but I feel like I'm reinventing the wheel here

$$\frac{\text{loss}_1}{\text{loss}_0}\approx1-\frac{\operatorname{Tr}(H^2)^2}{\operatorname{Tr}(H^3)\operatorname{Tr}H}$$

where $$H=A^TA$$

• This question is limited to an iterative solver, right? Mar 3 at 17:58
• Yes, because I don't believe there exist non-iterative solvers which can work on dense large matrices with $d$ in the billions Mar 3 at 18:03
• In practice, I agree. But since I am coming from the world of fast direct methods (with ~20M unknowns dense matrix solved using "compressed matrix" techniques arising from Maxwell's equations) I had a theoretical question in my mind for my purposes. Mar 3 at 18:12
• One relevant reference I have is this post by Higham which contains an overview of talks on exascale from a certain conference. I encountered questions along this line of thinking in the context of exascale numerical linear algebra. With this presentation from Eric Carson on iterative linear algebra in exascale era being the closest. Mar 3 at 18:17