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?

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

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?

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

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?

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

Re: Thomas algorithm number operations