University:
Whitman College
Course:
MATH-467 | Numerical Analysis
Academic year:

2023
Views:

324

Pages:

1
Author:

Clay Graves

Flop Counts: Gaussian Elimination For Gaussian elimination, we had the following loops: k 1 2 3 .. . j 2 : n = n − 1 rows 3:n=n−2 4:n=n−3 .. . Add/Sub Flops (n − 1)n (n − 2)(n − 1) (n − 3)(n − 2) .. . Mult/Div Flops (n + 1)(n − 1) n(n − 2) (n − 1)(n − 3) .. . k + 1 : n = n − k − 1 (n − k)(n − k + 1) (n − k + 2)(n − k) .. .. .. . . . k .. . n−1 1·2 n:n=1 1·3 Recall the following summation formulas: m X 1 = m, k=1 m X k= k=1 m(m + 1) , 2 m X k2 = k=1 m(m + 1)(2m + 1) 6 Now sum the Add/Subtract flops together: n−1 X (n − k)(n + 1 − k) = k=1 n−1 X (n2 + n − 2nk − k + k 2 ) = k=1 (n2 + n) n−1 X 1 − (2n + 1) k=1 n−1 X k+ k=1 n−1 X k2 = k=1 1 1 (n − 1)n (n − 1)n(2n − 1) + = n3 − n 2 6 3 3 Similarly, for the Multiply/Divide operations: (n2 + n)(n − 1) − (2n + 1) n−1 X (n − k)(n − k + 2) = k=1 n−1 X (n2 + 2n − 2nk + 2k + k 2 ) = k=1 (n2 + 2n) n−1 X k=1 1 − (2n − 2) n−1 X k=1 k+ n−1 X k2 = k=1 (n − 1)n (n − 1)n(2n − 1) 1 5 17 + = n3 + n2 − 2 6 3 2 6 Adding them together, the total flop count is (using big-oh notation): (n2 + 2n)(n − 1) − (2n − 2) 2 3 n + O(n2 ) 3

Flop Counts Gaussian Elimination - Study Guide

Related Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock