4
$\begingroup$

I wish to solve a linear system $A x =b$ in which $A$ is dense but not too large, say no larger than $10\times10$. However, I am not interested in the full solution vector $x = [x_0, x_1, \dots]$, rather I only care about accurately determining $x_0$. I know that Cramer's rule can compute $x_0$ directly, but this requires the evaluation of two determinants. It is my understanding that calculating these determinants is not typically faster than solving the full linear system, and is also more susceptible to catastrophic cancellation.

Are there algorithms for determining $x_0$ alone whose expected computational complexity beats Gaussian elimination or LU factorization? Does the answer change if I am willing to accept an approximation for $x_0$, say from an iterative approach?

Edit:

I'll provide some additional context, which might help stimulate some ideas. In my application, I have a sequence of linear systems $A^{(n)} x^{(n)} = b^{(n)}$, with $n=1,2,\dots$ being the dimension of the system. Concretely, $$ A^{(1)} x^{(1)} = b^{(1)} \to a_{00} x^{(1)}_0 = b_0 \\ A^{(2)} x^{(2)} = b^{(2)} \to \begin{bmatrix} a_{00} & a_{01} \\ a_{10} & a_{11} \end{bmatrix} \begin{bmatrix} x^{(2)}_0 \\ x^{(2)}_1 \end{bmatrix} = \begin{bmatrix} b_0 \\ b_1 \end{bmatrix} $$ and so on, with each linear system in the sequence simply appending another row and column to $A$ and appending an element to $b$, leaving the lower-order elements intact. As this sequence progresses, the value of $x_0^{(n)}$ should converge toward some limiting value $x^{(\infty)}_0$. So if it is possible to use the results of lower-order calculations $x^{(1)},\dots,x^{(n-1)}$ to compute $x_0^{(n)}$ in better than $O(n^3)$ time, that would be a useful answer as well.

$\endgroup$
8
  • 1
    $\begingroup$ I think if the matrix is sparse, there are some tricks that can be used to lower the computational cost, but not the complexity. But if it is dense, I don't know any methods which can achieve what you want. $\endgroup$ Sep 18 at 6:34
  • $\begingroup$ There is an $O(n^3)$ implementation of Cramer's rule, although I don't know if it would work in your case:. Ken Habgood; Itamar Arel (2012). "A condensation-based application of Cramerʼs rule for solving large-scale linear systems". Journal of Discrete Algorithms. 10: 98–109. doi:10.1016/j.jda.2011.06.007. $\endgroup$
    – nicoguaro
    Sep 18 at 13:34
  • 3
    $\begingroup$ Apparently we need to find $x_0$ for many different cases. Is there anything in common for matrices A and vectors b for those cases? Or those are completely unrelated? I am wondering if it is possible to find $x_0$ for one given A,b and then to use that information for updated A and/or b. $\endgroup$ Sep 18 at 14:07
  • $\begingroup$ Is $A$ special in any way? Symmetric, positive, non-negative, Hermitian, &c? $\endgroup$
    – Richard
    Sep 18 at 15:03
  • $\begingroup$ @MaximUmansky Very sharp observation. I've expanded the question to include more context about the problem which may help stimulate ideas along the lines of what you're thinking. $\endgroup$
    – Endulum
    Sep 19 at 2:30
4
$\begingroup$

In general, I think that the answer to your question about computing a single component is negative (unless you allow for Strassen-like methods, which technically are a positive answer since they have lower complexity than LU/Gaussian elimination). The best way to compute determinants in practice is via Gaussian elimination, so that saves you nothing. (Also, note that the biggest issue with Cramer's rule is not cancellation but overflow/underflow).

However, your edit has a better answer than the original problem.

You can update most matrix factorizations in $O(n^2)$ after adding a column and/or a row to the matrix (or, in general, after a rank-1 update). In real life, this is usually done with QR and/or Cholesky rather than other factorizations, for stability reasons; look for qrinsert in your language of choice; e.g. Python Matlab.

So in your iteration when you enlarge the system at each step you can solve the full linear systems while paying $O(n^2)$ per step, by relying on factorization updates: at each step, you update the factorization by adding a row ($O(n^2)$), then adding a column ($O(n^2)$), then you use the factorization to solve the linear system ($O(n^2)$).

$\endgroup$
1
  • $\begingroup$ Lovely answer! QR insertion seems like exactly what I want. And after a cursory search, it seems like there are a handful of Fortran implementations as well. $\endgroup$
    – Endulum
    Sep 20 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.