Results 1 to 7 of 7

Math Help - Thomas algorithm number operations

  1. #1
    Member
    Joined
    Nov 2010
    Posts
    164

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

    Re: Thomas algorithm number operations

    Quote Originally Posted by Darkprince View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2010
    Posts
    164

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

    Re: Thomas algorithm number operations

    Quote Originally Posted by Darkprince View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Nov 2010
    Posts
    164

    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?
    Last edited by Darkprince; November 24th 2011 at 07:34 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

    Re: Thomas algorithm number operations

    Quote Originally Posted by Darkprince View Post
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Nov 2010
    Posts
    164

    Re: Thomas algorithm number operations

    Thank you!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Algorithm and elementary operations
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 30th 2011, 09:25 AM
  2. I dont understand thomas algorithm...
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: October 20th 2010, 10:27 AM
  3. Bit operations algorithm question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 16th 2010, 01:10 PM
  4. perform basic operations on large numbers algorithm?
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: October 17th 2008, 09:50 AM
  5. A question from Number Theory book of Thomas Koshy?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 11th 2007, 07:48 AM

Search Tags


/mathhelpforum @mathhelpforum