Re: Question about LU decomposition

[Jaroslav Hajek]

On Mon, Apr 19, 2010 at 8:12 PM, Carlo de Falco <address@hidden> wrote:
>
> On 19 Apr 2010, at 15:31, forkandwait wrote:
>
>> Hi all,
>>
>> Let A = [2 4; 4 11].
>>
>> Then the output from the lu command is
>>
>> L = [1 0; 1/2 1]
>> U = [4 11; 0 -3/2]
>> P = [0 1; 1 0]
>>
>> This is great... but it is different from what would be generated if
>> the
>> permutation hadn't been done first, which would have been
>>
>> L = [1 0; 2 1]
>> U = [2 4; 0 3]
>>
>> This difference wouldn't be a problem, except I am just starting to
>> work
>> through Gilbert Strang's "Intro to Applied Mathematics" using the
>> computer as a
>> crutch (^H^H learning tool), and Octave's answers don't match the book
>> (generally because he doesn't permute the matrices).  (This matrix
>> is on p 20).
>>
>> I am not sure what my question is exactly, but maybe for starts:
>>
>> (1) is there a way to run lu() without permuting?
> yes but it is a dirty hack and is  only (questionably) useful if you
> want to check theoretical results:
>
> [l, u] = lu(sparse(A), 0);
> full(l)
> full(u)
> full(l*u-A)
>
>> (2) what is the long story on permuting and LU decomposition -- is
>> it wrong to
>> not permute?  Is there a relationship between all the possible
>> decompositions?
>> etc etc (a link would be awesome...)
> in general it is always a good idea to use pivoting (i.e. "permuting")
> to improve the numerical stability
> of the algorithm, and it has an almost negligible cost, so avoiding
> pivoting never makes sense in numerics.
>
>> Thanks again
>


Oh no, this is really overgeneralized. For instance, pivoted QR
typically takes 50% more time than plain QR. Rank-1 updates are also
typically more efficient (and simpler) without pivoting. But it is
true that unpivoted LU is very seldom used. LAPACK doesn't even have a
subroutine for this.

-- 
RNDr. Jaroslav Hajek, PhD
computing expert & GNU Octave developer
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz