1

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?

user14717
  • 2,155
  • 13
  • 14

1 Answers1

5

This algorithm is most useful for two situations, which are related to each other in practice:

  1. You don't know the matrix entries explicitly, but instead can only compute matrix-vector products with the matrix (often called "matrix-free")
  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.
Reid.Atcheson
  • 3,283
  • 15
  • 17
  • 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? – user14717 May 08 '19 at 16:03
  • 1
    To put another way: finding the condition number of a matrix is almost always equally as difficult as solving linear systems with that matrix.

    So the best you can do, usually, is try to recover conditioning information during a solution process. This is often possible with rank-revealing factorizations. But if you can't do this, then your next best option is to feed your solve function as an input to the Higham estimator and hope for the best.

     – Reid.Atcheson May 09 '19 at 01:01