[Scilab-Dev] O(n²) substitution for triangular systems

[Serge Steer]

As far as I know there is no triangular matrix detection implemented in
Scilab. The difference in execution time when the system is lower or
upper triangular is probably due to the fact that with lower triangular
the lu factorization cost almost nothing....

Serge Steer

Jean-Pierre Dussault a écrit :
> Hi,
>
> I need to solve linear equations involving iteratively several RHS. I
> wish to solve the triangular systems, for example LU factors or R'R
> Cholesky factors, in O(n²) complexity. It seems possible for _/some
> lower/_ triangular systems, but not for upper triangular involving U,
> L' and R, neither for lower triangular involving U'. In those cases, I
> obtain O(n³) complexity. I ran the following script in scilab 5.2.2:
>
>     n=[500,1000,2000];
>
>     for i=[1:3],
>        M=rand(n(i),n(i))+eye(n(i),n(i));
>        e=rand(n(i),1);
>        tic;[L,U,E]=lu(M);tlu(i)=toc();
>        tic;L\e;tL(i)=toc();
>        tic;U\e;tU(i)=toc();
>        tic;L'\e;tLp(i)=toc();
>        tic;U'\e;tUp(i)=toc();
>
>        M=M*M'+eye(n(i),n(i));
>        tic;[R]=chol(M);tchol(i)=toc();
>        tic;R\e;tR(i)=toc();
>        tic;R'\e;tRp(i)=toc();
>     end
>
>     [tlu,tL,tU,tLp,tUp,tchol,tR,tRp]
>     ans  =
>      
>         1.022    0.014    0.242    0.217    0.23     0.095    0.139   
>     0.041 
>         1.166    0.082    0.869    0.931    0.929    0.47     0.966   
>     0.11  
>         8.202    0.303    7.11     7.747    8.311    3.479    7.702   
>     0.438 
>
> Clearly, only L\e and R'\e are O(n²). I suspect a bug in detecting
> triangular systems.
>
> Is there a way to force solutions of triangular systems to be
> performed O(n²) substitution algorithms?
>
> Thx,
>
> JPD
>