2
$\begingroup$

I could not find a big-oh cost for Doolittle's algorithm for LU decomposition of a matrix online, so I took a pseudocode implementation from here and analyzed it to get $$\frac13n^3+\frac32n^2+\frac16n$$ operations.

However, the same document states here that there are in fact $$\frac23n^3+\frac12n^2+\frac16n$$ operations.

I triple checked my analysis, and couldn't see where I went wrong, so I ran the following Python code:

def doolittle_complexity(n):
   ops = 0
#  for i=1,⋯,n
   for i in range(1, n+1):
#     for j=1,⋯,i−1
      for j in range(1, i):
#        α=aij
         ops += 1
#        for p=1,⋯,j−1
         for p in range(1, j):
#            α=α−aipapj
             ops += 1
#        aij=αajj
         ops += 1
#  for j=i,⋯,n
   for j in range(i, n+1):
#      α=aij
       ops += 1
#      for p=1,⋯,i−1
       for p in range(1, i):
#         α=α−aipapj
          ops += 1
#      aij=α
       ops += 1
   return ops

print([(i, doolittle_complexity(i), i/6+((3*(i**2))/2)+i**3/3) for i in range(21)])

It defines a method that adds 1 to an operation counter every time the pseudocode algorithm would have done arithmetic or assignment. Then, it prints out a list containing tuples in the format (matrix size, # of operations counted, # of operations expected by my polynomial).

When run, it outputs:

[(0, 0, 0.0), (1, 2, 2.0), (2, 9, 9.0), (3, 23, 23.0), (4, 46, 46.0), (5, 80, 80.0), (6, 127, 127.0), (7, 189, 189.0), (8, 268, 268.0), (9, 366, 366.0), (10, 485, 485.0), (11, 627, 627.0), (12, 794, 794.0), (13, 988, 988.0), (14, 1211, 1211.0), (15, 1465, 1465.0), (16, 1752, 1752.0), (17, 2074, 2074.0), (18, 2433, 2433.0), (19, 2831, 2831.0), (20, 3270, 3270.0)]

Which seems to indicate that my polynomial was correct.

Regardless, and even though I understand that they have the same big-oh cost of $O(n^3)$, I would still like to understand how they arrived at their polynomial.

$\endgroup$
  • $\begingroup$ Are the links in the question working? $\endgroup$ – Shreesh Mar 15 '16 at 7:31
  • 1
    $\begingroup$ Have you triple-checked their analysis? If your polynomial is correct, theirs must be wrong. Do you expect us to dig through that paper for you? (Good job on the analysis, by the way!) $\endgroup$ – Raphael Mar 15 '16 at 7:34
  • $\begingroup$ There are two main possibilities. One is that you are analyzing different variants of the same algorithm, and so getting different results. The other is that one of you made a mistake. (Papers are full of mistakes.) If you're confident in your analysis, then just go with it. $\endgroup$ – Yuval Filmus Mar 15 '16 at 7:42
  • $\begingroup$ In that case, does anyone know where I can find a working version of Doolittle's? The other reason I believe I am wrong is that I have seen (2/3)n^3 elsewhere for the complexity of similar and dependent matrix operations. $\endgroup$ – ericmarkmartin Mar 15 '16 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.