Homework answers / question archive /  Linear Algbra Guide to MATLAB Assignment 4: Operation Counts for Gauss-Jordan Elimination Overview

 Linear Algbra Guide to MATLAB Assignment 4: Operation Counts for Gauss-Jordan Elimination Overview

Business

Share With

 Linear Algbra Guide to MATLAB Assignment 4: Operation Counts for Gauss-Jordan Elimination Overview. Arithmetic operations often constitute the most serious cost of performing a scientific computation. In this assignment arithmetic operations for the Gauss-Jordan elimination algorithm, as implemented in rref 337.m, are counted. As in the previous assignment, the code for the MATLAB function function [A,pivot.cols,pivot_count] - rref337 (A) is provided. The assignment is to modify this function so that the modified function also returns counts of arithmetic operations. Problem 4.1: Counting arithmetic operations in Gauss-Jordan. Modify rref 337 to (1) to have the name rref337 count, (2) to return additionally the number of floating-point addition and subtraction operations per- formed, (3) to return additionally the number of floating-point multiplication and division operations per- formed. Two kinds of floating point operations are considered. The first kind, reported in the return variable addsub, is the number of additions and subtractions performed. The second kind, reported in the return variable muldiv, is the member of multiplications and divisions performed. The function declaration for the new function should be as follows. function [A, pivot_cols,pivot_count, addsub,muldiv] - rref337 count (1) That is, addsub and muldiv should be added to the list of return variables. Counting arithmetic operations. At the beginning of the modified function rref 337count, initial- izing two accumulation variables addsub and muldiv to zero is appropriate. addsum - 0; muldiv - 0; As row operations are performed, the number of arithmetic operations of the two types is then added to these variables. Each row operation must be analyzed to determine how many arithmetic operations of each kind are used to implement the operation. 2 • Each replacement operation, implemented with SUB in rref337, multiplies each element in a row by a scalar and then subtracts the result from another row. If the row has length n there are then n multiplications and n subtractions. Hence, following the replacement operations in the forward phase, it is appropriate to insert code to count the arithmetic operations: 1 - SUB(A,pivot.count, A(tr, pcc)/A(pivot_count,pec), tr); addsub - addsub + n; muldiv - muldiv + n + 1; Note: Here muldiv is incremented by n+1 as an extra division, Actr,pce)/A(pivot.count,pce), is needed to compute the multiplier. • The interchange operations, implemented with SWAP in rref337, require no arithmetic; hence, they do not contribute to the operation counts considered here. The scaling operations, implemented with SCALE in rref337, multiply each of the n elements of the row by a multiplier. Moreover, there is an additional division required to compute the multiplier. Hence, code is appropriately inserted following each scaling operation to increment muldiv by n+1. . In the backward phase no arithmetic operations are needed to compute the multipliers since pivots have previously been scaled to equal 1. Hence, each elimination in the backward phase requires only n multiplications/ divisions as well as n additions/subtractions). Following each replacement operation in the backward phase it is appropriate to insert code to increment both addeum and muldiv by n. A test case. Consider the pen and paper calculation for A - [ 1 2 3; 4 5 6; 7 8 9]. The mumber of columns is n - 3. To facilitate counting, each each row operation is exhibited separately. . 1 2 3 .fi 2 xl |:::::: 2 -3 8 3 6 [1 2 3 + X-O-3-6 0 0 0 2 1 2 3 0 1 2 → 0 0 0 10-1 0 1 0 0 0 1 0 0 1 D D 7 8 9 0 -6-12 addsub=0 muldiv=0 addsub = 3 muldiv. 4 addsub 6 maldiv = 8 addsub = 9 wuldiv - 12 addsub = 9 muldiv = 16 adds ab = 12 wuldiv - 19 addsub 12 muldiv = 23 Each elimination step in the forward phase requires 3 additions / subtractions to subtract one row from another and 4 multiplications/divisions. Each scaling step requires no additions/subtractions but 4 mul- tiplications/divisions. Each elimination step in the backward phase requires 3 additions/subtractions and 3 multiplication/divisions. The very last row operation seems unncessary as it is to scale the first pivot which is already 1. The code in rref337count.m however does not test the values of the pivots before scaling them; hence, this row operation has no effect but will be performed nonetheless. Optional sections. The material below is not needed to complete MATLAB Assignment 4, but it introduces topics and techniques of importance in both the theory and practice of solving systems of linear equations. OPTIONAL: Operation count in a special cae. Suppose that each column has a pivot. (This can happen only ifm > n.) Then elimination under the first pivot requires m-1 eliminations, elimination under the second pivot requires --2 eliminations, ..., elimination under the last pivot requires men eliminations. Hence, the total number of eliminations in the forward phase is m-) = mn Σι = mm n(n+1) 2 21(2m -n-1). Each eliminations requires (as implemented above) n additions/subtractions and n+1 multiplications /divisions; hence, the total arithmetic cost of the forward phase is snº(2m - n - 1) additions/subtractions and In(n + 1)(2m - n - 1) multipliations divisions. In the backward phase we normalize each pivot which requires n scaling operations at a total cost of n(n+1) multiplications/divisions (as implemented above). The number of eliminations in the backward phase will be the same as in the forward phase but the mmber of multiplications/divisions per elimina- tion is reduced by 1 because the pivots are normalized. Hence, the arithmetic cost of elimination in the backward phase is knº(2m-n-1) additions/subtractions and ?nº (2m-n-1) multipliations /divisions. Hence, the total number of multiplications divisions for the backward phase is n(n+1) + *** (2m – 1 – 1) = n(m- n( Altogether the arithmetic cost of the Gauss-Jordan elimination algorithm, both the forward and back- ward phases, in the code in rref 337 is additiona/subtractions = n(2m-1-1) = m2 [2m - n) +n - 1] multiplications /divisions = n(n+1) (m, n) + + žin + 1) Note: The number of both kinds of operations is approximately proportional to n for large n. => [cm – n)n + gx2 + 3x + 1] + OPTIONAL: Comment on more efficient implementation. The code developed in this assign- ment counts arithmetic operations for the Gauss-Jordan elimination algorithms as implemented in rref337... This implementation, however, can be said to contain a significant amount of unnecessary arithmetic. For example, consider the third row operation in the test case above. Here we rewrite the operation with all the arithmetic operations shown explicitly: 2 3 2 3 1 2 3 . 0-3 -6 0 -6 0 -3 -6 0 -6 -12 0-2-0-6-2-(-3) -12 -2.(-6) 0 0 0 -bo Notice that arithmetic operations used in the computation of the first two components of the third row are wasted in the sense that the value of these components was known to be zero before the computation was done. The first component was necessarily zero as the first component of each row involved in the calculations was zero as a result of the earlier steps of the calculation. The second component was destined to be zero as that component was the target of the elimination. The code for the forward phase can be easily rewritten to avoid this unnecessary computation. A(tr,pec) - 0.0; mult - A(tr,pec)/(pivot_count,pec); A(tr,pce+1:n) - A(tr,pce+1:n) - mult-A(pivot_count,pec+1:n); addsub - addsub + n - pce; muldiv - muldiv + n - pee + 1; Because only entries to the right of the last pivot found need be processed, the number of addi- tions/subtractions and the number of multiplications/divisions have both been reduced by pee (the column index of the pivot just found). With careful coding of this kind it is possible to approxi- mately halve the amount of arithmetic required to perform Gauss-Jordan elimination. The amount of arithmetic, however, remains proportional to n.