# Missing something fundamental about condition number estimation

In Higham's Accuracy and Stability of Numerical Algorithms, Chapter 15, algorithm 15.3 and 15.4: The topic is ostensibly condition number estimation, but these algorithms show how to compute $$\gamma$$ such that $$\gamma < \left\|A\right\|_{1}$$.

But if I have a matrix $$A$$, I already know how to compute $$\left\|A \right\|_1$$, just compute $$\left\| A \right\|_1 = \max_{j} \sum_{i} |a_{ij}|$$ That's a quick $$O(n^2)$$ flops. So the hard part is computation of $$\left\|A^{-1}\right\|_1$$.

Ok, so maybe I should read it as $$A \mapsto A^{-1}$$. Then algorithm 15.3 tells me to compute $$y = A^{-1}x$$, or in other words solve $$Ay = x$$. This isn't cheaper than solving the linear system. Is it assumed that $$A$$ is already decomposed into triangular factors?

What am I missing?

2. You want the 1-norm for the inverse of a matrix. The inverse of a sparse matrix is typically dense, and since sparse matrices tend to be gigantic this turns the $$O(n^2)$$ algorithm you just described into an intractable computation. Generally this means you precompute a factorization and use the corresponding solve as the matrix-free evaluation of the inverse operator.
• Ok, so if I understand correctly, it is rare that you can get $\kappa(A)$ cheaply before solving a linear system-most often you can only get it cheaply as a byproduct of computing what you want. Is this interpretation correct? May 8 '19 at 16:03