Prev: Data Brush Tool
Next: how to add sine to sound signal
From: John D'Errico on 31 Mar 2010 12:19
"Roland Kruse" <roland.kruse(a)uni-oldenburg.de> wrote in message <hovr9a$97e$1(a)fred.mathworks.com>...
> > You cannot tell me that this is not fast.
> > John
>
> Sure it is fast, and yes, A is SPARSE.
> However, I need to execute the
> x = Q*(U\(L\(P*(R\y))));
> line for a lot of times (let's say 1E6).
>
> What actually suprised me is that simply calling x = A\b repeatedly is not that much slower than using the above approach (which, as said, is approx. 2-3 times faster for my data).
> In other words, Matlab solves tridiagonal systems very efficiently. Therefore I wondered if there's a specific solution for my (tridiagonal) problem: the LU decomposition is a more general approach and may consequently be not optimal.

You might try Tim's solvers on the FEX.

I might also suggest an alternative that depends
on your matrix A. Most of the time there may be
little reason for pivoting on a tridiagonal matrix.
So why bother?

The simple, un-pivoted LU is much faster, plus
there will be no need to unscramble the results
afterwards.

John
From: Roland Kruse on 31 Mar 2010 17:22
OK, thanks everybody, learnt something today.
The situation so far (a little benchmark):
Let A be [10000*10000], SPARSE, tridiagonal, filled with complex randn
Let's solve Ax=b for n=2000 RHS vectors b=randn(10000,1)

1) Dumb solution: execute A\b n times
7.4 sec.
2) If one knows all b beforehand: put b's in matrix B and use A\B
1.8 sec.
3) Use Matlab's [L,U] = lu(A) & x = U\(L\b)
8.4 sec
4) Use Matlab's [L,U,P,Q,R] = lu(A) & x = Q* (U\ (L\ (P*(R\b))))
2.5 sec
5) Use Thomas algorithm for LU decomposition of A & x = U\(L\b)
1.8 sec

Conclusion:
- Matlab's A\B works very well
- Matlab's [L,U] = lu(A) is no good for tridiagonal systems
- Current best solution for my problem is the Thomas algorithm
- Approx. 4 times increase in speed
First  |  Prev  | 
Pages: 1 2
Prev: Data Brush Tool
Next: how to add sine to sound signal