File Exchange

## Fast Tridiagonal System Solver

version 1.0 (2.04 KB) by

A fast tridiagonal system solver.

Updated

Solves a tridiagonal system quickly.

John D'Errico

### John D'Errico (view profile)

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.

Rob

### Rob (view profile)

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.

Xiang

### Xiang (view profile)

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.

Vinesh Rajpaul

### Vinesh Rajpaul (view profile)

Great script. Easy to use and works very well.

Hongjun Zhang

### Hongjun Zhang (view profile)

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.

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

Alex Prideaux

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

Jorge Puebla

Edgar Guevara Codina

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

sebastian swose

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

sarava shanmuga

Bill Armstrong

The hidden photos were very tastefully done...

Garner Izru

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