Code covered by the BSD License  

Highlights from
Fast Tridiagonal System Solver

4.0

4.0 | 14 ratings Rate this file 41 Downloads (last 30 days) File Size: 2.04 KB File ID: #1359

Fast Tridiagonal System Solver

by

 

A fast tridiagonal system solver.

| Watch this File

File Information
Description

Solves a tridiagonal system quickly.

Acknowledgements

This file inspired Fast Pentadiagonal System Solver and Block Tridiagonal Solver.

MATLAB release MATLAB 5.2 (R10)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (16)
17 Sep 2012 John D'Errico

It looks like those who think this is an efficient tool (Hongjun, etc.) and therefore give it a good rating, don't understand how to use sparse matrices in MATLAB. In fact, a couple of those people talk about using inv. SIGH.

In fact, this tool REALLY is considerably slower than backslash, as long as you understand what you are doing. If you have no idea what you are doing, then quite likely you are using the wrong tools in MATLAB in any event.

n = 1000000;

B = rand(n,3);
B(:,2) = B(:,2) + 1;
A = spdiags(B,-1:1,n,n);

d = rand(n,1);

a = B(:,2);
b = B(2:n,3);
c = B(1:n-1,1);

tic
xt = thomas(a,b,c,d);
toc
Elapsed time is 1.727341 seconds.

tic
xs = A\d;
toc
Elapsed time is 0.125294 seconds.

See that thomas was roughly 14 times slower than backslash on the same problem. This is a major difference. backslash was more efficient for ANY size matrix, ranging from 5 to 20 times as fast in my tests on different size matrices.

Someone will be sure to think that I've not included the time to generate the sparse matrix itself, but the call to spdiags itself took only about 0.5 seconds. So even if I combine the two calls, it still is twice as fast to use backslash. If you will do other things with the sparse matrix A, then the call to spdiags is arguably spread across all the work you do, so it is more efficient yet.

The point is, there really is no need for thomas to exist at all, as far batter tools are available in MATLAB. Use backslash. And for gods sake, do NOT use inv.

17 Sep 2012 Muhammad Atif  
23 Jun 2012 Rob

I rewrote this with all of the matrix operations in the form of operators on A(:,i) rather than on A(i,:). As a result it does large cases such as 5000 instances of a 5000x5000 array about 13x faster. Presumably this is because MATLAB stores data by columns.

08 Dec 2009 Xiang

My test result is the same as Tim's and Alex's. My A matrix is only 20*20 and is strictly diagonally dominant tridiagonal.
It took "thomas(A,B)" 62.7 seconds to complete 4000 time-steps, while "A\B" used only 4.5 seconds.

23 Mar 2009 Vinesh Rajpaul

Great script. Easy to use and works very well.

04 Mar 2009 Hongjun Zhang

Excellent algorithm. I tested it on 2000x2000 matrix, it's 10 times faster than back slash and 5 times faster than inv(), on 2.0G Intel Duo Core, 1G ram, on Matlab 8a. (1.2 seconds for thomas, 6.5 s for inv(), and 13.5 for /).

For small matrix, say 100x100, these three are comparable.

I though Tim was right and trusted back slash. But it's not the case for me.

I don't know what kind of sparse matrices Tim and Alex talking about that back slash runs faster for. I would say the 3-diagonal is already sparse and is encounter often in solving pdes.

08 Dec 2007 Tim Davis

This function is superseded by the tridiagonal solver that is now built into MATLAB (x=A\b). For x=thomas(A,b) where A is sparse and tridiagonal, x=A\b is up to 25,000 times (!) faster than this code. For x=thomas(amain,aup,alo,b), this function is about 30 times slower than x=A\b.

So the only reason for this code is to illustrate the algorithm - for which its still useful. But don't expect to get great performance from it compared to x=A\b in MATLAB 7.5

17 Nov 2007 Alex Prideaux

Using Matlab 7.4 and sparse matrices, this code is unfortunately at least 10 times slower than the standard Matlab backslash.

04 May 2007 Jorge Puebla

I received a recommendation about this file, is an excelent tool

03 May 2007 Edgar Guevara Codina

Very fast, it helped me improve the algorithm of a FD-BPM simulation

28 Apr 2007 sebastian swose

The solving of a linear system with calculating the inverse matrix is faster!!??
I dodnt know why

30 Nov 2006 sarava shanmuga  
18 Nov 2006 Bill Armstrong

The hidden photos were very tastefully done...

28 Apr 2006 Garner Izru

Excellent! I was looking for a routine like this, thanks Frederico!

19 Feb 2004 Venkata Pradeep Indrakanti

This code works faster than others using the sparse matrix functions of MATLAB.Although the gain in speed might not be evident for small computations, for the bigger ones, it might save (valuable) time.

04 Jun 2003 abhijith bharadwaj

this programme was very good,super,extraordinary

Contact us