Actual computational complexity of solving a linear system accounting for numerical accuracy (digit)

Question

Solving a system of linear equations is solving for $n \times 1$ vector $x$ out of $Ax = b$, where $A$ is $n \times n$ matrix. Suppose that $A$'s entries have $k$ digits at maximum, in binary or decimal. Similarly, entries of $b$ also has $k$ digits at maximum.

It is said that computational complexity of solving lienar equation is $O(n^3)$, but this does not account for numerical issues - such as actually turning out $x$ to be accurate up to $y$ digits.

What would be actual computational complexity accounting for $k$ and $y$?

Answer 1

This is not a simple question to answer, and I doubt you will get a complete response here. If you want to do more reading on the subject, this a big part of numerical analsys/numerical linear algebra and there are many texts on the subject (Trefethen and Bau was the text I used). I am by no means an expert so perhaps some more experienced users will have better answers than this.

To get you started with some basic terminology:

A lot of numerical analysis makes the assumption that basic arithmetic can be done with an $1\pm \epsilon$ error. This $\epsilon$ is referred to as the machine precision.

The task is then to design algorithms which are numerically stable. Loosely, that a small change in the numerical input to the algorithm leads to a small change in the numerical output (relative to what the change would be if you could do everything exactly).

Solving linear systems is not well conditioned in general. That means that even in exact arithmetic, there are systems where the solution to $Ax=b$ and $\tilde{A}x=b$ are very different even if $\tilde{A}$ is very close to $A$. In such cases, there is no hope of a good numerical solution since we have to make a small perturbation to $A$ to represent it on a computer. The notion of condition number $\kappa(A)$ is used to measure "how ill-conditioned" a system is.

As to the time complexity, this depends heavily on what method you use. In general, direct methods will have the same time complexity and then some results about the accuraccy of the output (usually relative to $\epsilon \cdot \kappa(A)$).

On the other hand, iterative methods may require a different number of iterations to reach a prescribed accuracy when implemented with different amounts of precision. There are some theoretical bounds on convergence, but often time the actual convergence in practice is quite a bit better than the theoretical bounds. Similarly, depending on the algorithm, the highest accuracy you can attain may be lower than you would like. The study of how fast iterative algorithms converge, and to what level of accuracy is an active field of research.

Answer 2

I assume that you want to solve only one system $Ax=b$. We don't consider iterative methods but only the standard method of using the LU decomposition of $A$.

The complexity of calculating $x$ is essentially the number of used couples of operations $(+,\times)$ to obtain $L,U$, that is, $\sim n^3/3$.

How to choose $k$ ? If the condition number of $A$ is $10^r$, then choose $k=y+r$ and you will get $x$ with $y$ significant digits.

The complexity of a multiplication with $k$ digits is $\approx 2\log_2(10)k^2$ (a computer works in binary) elementary operations.

Finally the complexity is $\approx (2.2)n^3k^2=(2.2)n^3(y+r)^2$ elementary operations.