# Thomas algorithm number operations

• Nov 21st 2011, 11:59 AM
Darkprince
Thomas algorithm number operations
I have to find the number of operations needed by Thomas algorithm for an nxn tridiagonal matrix.

The Thomas algorithm is divided into two parts, the forward sweep and the back substitution.

The forward sweep is: c(i)' = c(1)/b(1) for i = 1 and c(i) / ((b(i) - c(i-1)' * a(i)) for i=2 to (n-1)

d(i)' = d(1)/b(1) for i = 1 and (d(i) - d(i-1)' * a(i) ) / ((b(i) - c(i-1)' * a(i)) for i=2 to n

The back substitution is x(n)=d(n)' and x(i) = d(i)' - c(i)' * x(i+1) for i=(n-1) to 1

Now, for the forward sweep I find that we need 2n-1 divisions, 3n-3 subtractions and 3n-3 multiplications. {Taking in account the operations for c(i)' and d(i)'}

For the back substitution I find that we need n-1 subtractions and n-1 multiplications.

My final answer is 10n-11 operations.

The thing is that in some books the number of operations is O(8n) but I don't really find where I have any mistake.

Can someone review my work please and enlighten me?
• Nov 23rd 2011, 09:29 PM
CaptainBlack
Re: Thomas algorithm number operations
Quote:

Originally Posted by Darkprince
I have to find the number of operations needed by Thomas algorithm for an nxn tridiagonal matrix.

The Thomas algorithm is divided into two parts, the forward sweep and the back substitution.

The forward sweep is: c(i)' = c(1)/b(1) for i = 1 and c(i) / ((b(i) - c(i-1)' * a(i)) for i=2 to (n-1)

d(i)' = d(1)/b(1) for i = 1 and (d(i) - d(i-1)' * a(i) ) / ((b(i) - c(i-1)' * a(i)) for i=2 to n

The back substitution is x(n)=d(n)' and x(i) = d(i)' - c(i)' * x(i+1) for i=(n-1) to 1

Now, for the forward sweep I find that we need 2n-1 divisions, 3n-3 subtractions and 3n-3 multiplications. {Taking in account the operations for c(i)' and d(i)'}

For the back substitution I find that we need n-1 subtractions and n-1 multiplications.

My final answer is 10n-11 operations.

The thing is that in some books the number of operations is O(8n) but I don't really find where I have any mistake.

Can someone review my work please and enlighten me?

You are counting the operations in ((b(i) - c(i-1)' * a(i)) twice.

CB
• Nov 24th 2011, 12:41 PM
Darkprince
Re: Thomas algorithm number operations
But ((b(i) - c(i-1)' * a(i)) is used twice. Once for finding c(i)' and then for finding d(i)'.
They are two different calculations i.e c(i)' = c(i) / ((b(i) - c(i-1)' * a(i)) for i=2 to (n-1)
and
d(i)' = d(1)/b(1) for i = 1 and (d(i) - d(i-1)' * a(i) ) / ((b(i) - c(i-1)' * a(i)) for i=2 to n

That's why I am counting it twice. So why to count it once?
• Nov 24th 2011, 01:21 PM
CaptainBlack
Re: Thomas algorithm number operations
Quote:

Originally Posted by Darkprince
But ((b(i) - c(i-1)' * a(i)) is used twice. Once for finding c(i)' and then for finding d(i)'.
They are two different calculations i.e c(i)' = c(i) / ((b(i) - c(i-1)' * a(i)) for i=2 to (n-1)
and
d(i)' = d(1)/b(1) for i = 1 and (d(i) - d(i-1)' * a(i) ) / ((b(i) - c(i-1)' * a(i)) for i=2 to n

That's why I am counting it twice. So why to count it once?

Because it can be calculated once and then reused.

CB
• Nov 24th 2011, 02:32 PM
Darkprince
Re: Thomas algorithm number operations
But they are two different loops, doesn't make a difference? How that is?

When the second loop is taking place, it "brings" the solution to its calculation? Is the solution stored?
• Nov 24th 2011, 08:48 PM
CaptainBlack
Re: Thomas algorithm number operations
Quote:

Originally Posted by Darkprince
But they are two different loops, doesn't make a difference? How that is?

When the second loop is taking place, it "brings" the solution to its calculation? Is the solution stored?

No; you store it when it is initially calculated

Code:

```c(i)' = c(1)/b(1);div(i)=1 for i = 1 and div(i)=(b(i) - c(i-1)' * a(i); c(i) / div(i) for i=2 to (n-1) d(i)' = d(1)/b(1) for i = 1 and (d(i) - d(i-1)' * a(i) ) / div(i) for i=2 to n The back substitution is x(n)=d(n)' and x(i) = d(i)' - c(i)' * x(i+1) for i=(n-1) to 1```
CB
• Nov 25th 2011, 06:08 AM
Darkprince
Re: Thomas algorithm number operations
Thank you!