Thread: 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?

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

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?

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

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?

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

Thank you!