Ok, I've been working on a matrix solver for a while (no, its not going well, thanks for asking), and just discovered something that worrys me alot;

The problem at hand is LU Decomposition of a square matrix, for example

$\begin{matrix} 1&2&3\\ 2&-1&1\\ 3&4&-1\\ \end{matrix}$

WolframAlpha's answer is completely different from the example source


$\begin{matrix} 1&2&3\\ 3&-2&-10\\ 2&2.5&20\\ \end{matrix}$


$\begin{matrix} 1&2&3\\ 2&-5&-5\\ 3&0.4&-8\\ \end{matrix}$

What's going on?

  • $\begingroup$ I think your example source has some problem. Compare equation (3) with equation (6). $A$ is supposed to equal $LU$... $\endgroup$ – Willie Wong Apr 17 '11 at 22:43
  • $\begingroup$ The Wolfram one also ends up being trying to take the LU decomposition of a row permutation of $A$. (It is the one for with the bottom two rows switched.) $\endgroup$ – Willie Wong Apr 17 '11 at 22:51
  • 1
    $\begingroup$ @Willie: The example source is correct. Equation (6) you're referring to is showing how to store the $LU$ decomposition efficiently in one matrix. $\endgroup$ – t.b. Apr 17 '11 at 22:52
  • $\begingroup$ @Theo: ah, thanks, I didn't pay enough attention. $\endgroup$ – Willie Wong Apr 17 '11 at 22:55
  • 2
    $\begingroup$ Also, I think the question statement has a typo. Entry $(2,2)$ of the Wolfram compact representation should be $-2$ instead of $-1$. $\endgroup$ – cardinal Apr 17 '11 at 23:02

It looks like Wolfram Alpha is doing an LU decomposition with partial pivoting. So, it's actually solving a system like $$\newcommand{\bm}[1]{\mathbf{#1}} \bm{P} \bm{A} = \bm{L} \bm{U} $$ where $\bm{P}$ is a permutation matrix.

Curiously, it appears that Alpha simply isn't listing the permutation used in solving the system. In this case it is $$ \bm{P} = \left( \begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix} \right) . $$

This is a common technique to enhance numerical stability.

You can recover $\bm{A}$ via $$ \bm{A} = \bm{P}^{-1} \bm{L} \bm{U} = \bm{P L U} $$ since in this case $\bm{P} = \bm{P}^{-1}$.

  • 1
    $\begingroup$ So both are correct but WA is swapping around A before decomposition? $\endgroup$ – Andrew Bolster Apr 17 '11 at 23:07
  • $\begingroup$ I didn't check closely the other solution, but the Wolfram one is correct when the permutation is included. $\endgroup$ – cardinal Apr 18 '11 at 0:00

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.