<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
Hi,<br>
<br>
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 <u><i>some
lower</i></u> 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:<br>
<blockquote>n=[500,1000,2000];<br>
<br>
for i=[1:3],<br>
M=rand(n(i),n(i))+eye(n(i),n(i));<br>
e=rand(n(i),1);<br>
tic;[L,U,E]=lu(M);tlu(i)=toc();<br>
tic;L\e;tL(i)=toc();<br>
tic;U\e;tU(i)=toc();<br>
tic;L'\e;tLp(i)=toc();<br>
tic;U'\e;tUp(i)=toc();<br>
<br>
M=M*M'+eye(n(i),n(i));<br>
tic;[R]=chol(M);tchol(i)=toc();<br>
tic;R\e;tR(i)=toc();<br>
tic;R'\e;tRp(i)=toc();<br>
end<br>
<br>
[tlu,tL,tU,tLp,tUp,tchol,tR,tRp]<br>
ans =<br>
<br>
1.022 0.014 0.242 0.217 0.23 0.095 0.139
0.041 <br>
1.166 0.082 0.869 0.931 0.929 0.47 0.966
0.11 <br>
8.202 0.303 7.11 7.747 8.311 3.479 7.702
0.438 <br>
<br>
</blockquote>
Clearly, only L\e and R'\e are O(n²). I suspect a bug in detecting
triangular systems.<br>
<br>
Is there a way to force solutions of triangular systems to be performed
O(n²) substitution algorithms?<br>
<br>
Thx,<br>
<br>
JPD<br>
<br>
</body>
</html>