Confused on Echelon Form

[tawny merlin]

I am incredibly confused on this homework for my linear algebra class, the worst case answer given seems to be incorrect no matter how I approach the problem.

[tawny merlin]

Here's my work trying to just get the equation to match with a 3x4 matrix

[tame dock]

The book’s flop formula (2/3 n^3 + 1/2 n^2 – 7/6 n) assumes the forward elimination phase only so you divide each entry below the pivot by the pivot once to get the multipliers then use those multipliers to update the rest of the row and you move on. It never rescales the pivot row to make the pivot equal to 1 – that scaling belongs to the back-substitution / reduced echelon step. In your 3x4 run you did extra “Rk <- Rk / pivot” divisions so you counted more flops (22) than the forward phase worst case count (19). If you redo the elimination without those pivot row divisions you will hit the textbook 19 flop total and the later “at most n^2 extra flops” bound will cover the scaling and back elimination needed to reach reduced row echelon form.

[tawny merlin]

Are operations where the result would be zero not counted?

[tame dock]

In flop counts you count every arithmetic step you actually have to execute even if the number you end up writing happens to be 0

[tawny merlin]

The only way I was able to get the answers to match was to assume that when canceling terms in a row their sums do not count towards the flop count

[tame dock]

The textbook formula treats the matrix as completely dense

Wvery entry in the part you are working on is assumed non zero so you still have to do the multiply subtract pair even if the final number happens to cancel to 0

Only if you can see in advance that an entry is structurally zero (for example the matrix is already triangular or explicitly sparse) do you skip the step and leave it out of the flop count. By deciding not to count the “cance to zero” updates you turned your run into a special sparse case so its no longer the worst case scenario the formula is measuring

[tawny merlin]

Im saying that when you add a scaled row to another row to cancel the leading term, you only count the flops required to compute the entries of the new row which did not include the leading term

[tame dock]

In the classic worst case count you loop through every column j = k … n when you do
a_ij = a_ij – m * a_kj
That includes j = k even though that update turns a_ik into 0. The two flops (one multiply, one subtract) are still executed so they are included in the 2 flops × (n–k+1) number for that row. If you skip j = k and only update j = k+1 … n you save one multiply subtract pair per row below the pivot and the total flop formula changes (you get 2/3 n^3 – 1/2 n^2 – 1/6 n instead of 2/3 n^3 + 1/2 n^2 – 7/6 n). Textbooks choose the dont skip anything version to keep the algebra clean and to match how dense matrix code often works (its cheaper to run one uniform loop than branch on j = k).

[tawny merlin]

It seems like youre saying the formula the book gives seems to match with the not skipping algorithm but if you try it out on a 2x3 matrix it seems to agree with the value given by skipping

Maybe Im misunderstanding, are you talking about specifically the leading term which is cancelled or the leading zeroes in each row as well?

[tame dock]

The books formula counts the forward pass this way: for each pivot column k you (1) compute the multiplier for every row below the pivot one division per row and (2) update only the entries to the right of that pivot so you never touch the pivot column again. That means the “zero that appears in the pivot column” is not updated just like your skip rule. What the book does not include is scaling the pivot row to make the pivot equal to 1, that step belongs to the later reduced echelon phase. With this convention the flop total is (2/3)n^3 + (1/2)n^2 − (7/6)n which gives 5 flops for a 2 by 3 matrix and 19 flops for a 3 by 4 matrix or the same numbers you get when you skip the pivot column but do not rescale the pivot row. If you also rescale each pivot row the count rises (22 flops in your 3 by 4 example) because those extra divisions are outside the scope of the textbooks forward elimination only tally

[tame dock]

I mean for each row below the pivot you still do one division to get the multiplier but you then update only the columns to the right of the pivot. So the entry that will become zero in the pivot column is not multiplied-subtracted. Any entries that are already zero from earlier steps are also skipped