Matrix nonzero elements

A diagonal matrix has nonzero elements only on the principal diagonal and zeros elsewhere. The unit matrix is a diagonal matrix. Large matrices with small matrices symmetrically lined up along the principal diagonal are sometimes encountered in computational chemistry. 

A tridiagonal matr ix has nonzero elements only on the pr incipal diagonal and on the diagonals on either side of the pr incipal diagonal. If the diagonals on either side of the principal diagonal are the same, the matrix is a symmetr ic tr idiagonal matr ix. 

Procedure. Subtraet xl from the input matrix above. Load the resulting upper semimatrix into MOBAS. The first element is 1,1,0.5,0. Reeall that MOBAS requires 600 of only the nonzero elements in the upper semimatrix. Obtain the eigenvalues and eigenveetors. 

This has zero value unless both sets n") and are identical with the set so the matrix is a diagonal one with only one nonzero element, and its trace is obviously unity. Such a matrix is called an elementary matrix, see Chapter 7, Eq. (7-92). 

Such a triangle additive scheme will be economical once we involve economical diagonal operators a = 1,2,..., m. Economical schemes arising in practical implementations of multidimensional mathematical-physics problems turn out to be triangle additive schemes (usually lower, but sometimes upper), whose matrices are of a special structure. As a rule, nonzero elements of the matrix (C ap) stand only on one or two diagonals adjacent to the main diagonal. With this in mind, the scheme... 

By contrast, Fig. 9c shows an alternative scheme using linked list. In this scheme (scheme II) the information associated with a nonzero element is stored in a triplet containing the row index, the value of the nonzero element, and a pointer to the address of the next element in the same column. The starting addresses of each column are stored in another n locations. Notice that in this scheme the successive elements need not be stored in consecutive locations. To insert or delete an element requires only the change of one or two pointers no rearrangement of the list is necessary. On the other hand, the storage requirement for the same matrix is now 3 N + n and, as it stands, to find a specific nonzero element requires a linear search through the chain. 

The next step is to divide the nonzero elements in the second row by the first nonzero element in the second row—the elements in the third and last columns. The second element in the second row is set to one. The calculation proceeds in this way from row to row with many fewer divisions and subtractions required to convert the matrix into the form with zero values below the diagonal and ones on the diagonal. When the conversion has finally been achieved, there are ones on the diagonal and nonzero values only in the last column and for the elements immediately to the right of the diagonal. 

The nonzero elements are those with both indices the same and are called the diagonal elements. The sum of the diagonal elements of a square matrix is called the trace... 

Modem LP solvers can solve very large LPs very quickly and reliably on a PC or workstation. LP size is measured by several parameters (1) the number of variables n, (2) the number of constraints m, and (3) the number of nonzero entries nz in the constraint matrix A. The best measure is the number of nonzero elements nz because it directly determines the required storage and has a greater effect on computation time than n or m. For almost all LPs encountered in practice, nz is much less than mn, because each constraint involves only a few of the variables jc. The problem density 100(nz/mn) is usually less than 1%, and it almost always decreases as m and n increase. Problems with small densities are called sparse, and real world LPs are always sparse. Roughly speaking, a problem with under 1000 nonzeros is small, between 1000 and 50,000 is medium-size, and over 50,000 is large. A small problem probably has m and n in the hundreds, a medium-size problem in the low to mid thousands, and a large problem above 10,000. 

To form the adjacency matrix in a simpler way, note that the elements of the first column of the adjacency matrix in Fig. 7b correspond exactly to the elements of the first column of the occurrence matrix in Fig. 6 if the output element is deleted. Similarly, the elements of column 2 of the adjacency matrix correspond exactly to the elements of the fourth column of the occurrence matrix if the output element is deleted. Therefore, if the columns of the occurrence were permuted until all of the output elements appeared on the main diagonal, as in Fig. 7a, the nonzero elements of the occurrence matrix... 

Actually, only one matrix need be stored if the adjacency matrix is stored initially and thereafter multiplied by itself. Matrix elements are replaced by the resulting product elements as they are computed. The product matrix obtained in this manner for the fcth power may contain some nonzero elements which correspond to paths longer than k steps instead of strictly k step paths, but this will not affect the final matrix obtained corresponding to the nth power, since these paths would eventually be identified in any case. All of the modifications to the methods of Section II mentioned above simplify the calculations needed to obtain the reachability matrix. The procedure for identifying the maximal loops given in Section II remains the same. 

The nonzero elements of a column, j, of the matrix P indicate the loops that are fed information by the equations of loop j, and the nonzero elements of any row, i, indicate the loops that feed information to loop i. The ordering procedure for the irreducible sets of equatins (maximal loops) is as follows ... 

When a loop is found by the above procedure, it may or may not be a maximal loop and it may or may not contain the set of equations that should be solved next in sequence. If the loop is maximal and contains the set of equations to be solved next in the sequence, it will not be fed information by any of the other equations of the reduced system, and, in the reduced matrix, the row corresponding to the loop will contain all zero elements. Therefore, when a loop is found and the reduced matrix is formed, the procedure returns to the first phase and removes the rows without nonzero elements. When a row corresponding to a loop is removed from the matrix, the set of equations that correspond to all of the rows that were combined to form the composite row of the loop are placed next in the precedence order. If no rows have all zero elements, the procedure continues with the second phase by tracing a new path starting with any row of the reduced matrix and considering only... 

Form a new j by n Boolean matrix, M(0) as follows For each zero entry in column k, reproduce the corresponding row as a row in M(0). For example, the second row of the occurrence matrix in Fig. 12a contains a zero in column k = 1 and therefore the element = 0, element — 1, to 3 = 0, and to 4 = 1 comprise the first row of M(0). The second row of M(0) would be exactly like the third row of that occurrence matrix. This process is continued until all of the rows with zero entries in column k have been included as rows of M(0). A final row is added to M(0), whch is the Boolean union of all of the rows in the occurrence matrix which contain nonzero entries in column k. For example, rows 1 amd 4 of the occurrence matrix contain nonzero elements in column 1 so that the elements of the last row of M(0) are m3I = 1, m32 = 0, m33 = 1, m34 = 0. Figure 13a illustrates M(0). 

A new matrix M(1) is formed from M(0) in the same manner that M(0) was formed from the occurrence matrix. The column of M<0) containing the most nonzero elements is identified, and M(1> is made up of rows identical to each row of M(0), which contains a zero in column k and one final row, which is the Boolean union of the remaining rows in M(0). Figure 13b illustrates M(1). A record is kept of which rows of the original occurrence matrix have been combined to form each row of M(0), M(1), and so on. 

New matrices M(2), M(3), etc. are formed until the matrix M(,) is obtained, which contains exactly one nonzero element in each column. Each row of the matrix M(n> corresponds to a subset of equations in the original system. Since each column of M(n) contains only one nonzero element, each variable of the system appears in only one subset of equations represented by the row in which the nonzero element appears. Therefore, the subset of equations represented by a row of M(n) is a disjoint subsystem. For example, the matrix M(1) illustrated in Fig. 13b has only one nonzero element in each column. 

For example, in the adjacency matrix of Fig. 14 we can start with the first row and trace a path from/j to fs because there is a nonzero element in row 1 and column 5. Then the path is traced from fs back to /t because of the nonzero element in row 5, column 7, yielding the loop /1-/5-/1. After this loop has been found, each path traced from the vertices in this loop will yeild a loop. We can return to the last equation found in the loop, /5, and trace a path from/5 to another equation that feeds it,/3. The path is then continued from /3 to the first equation that feeds it, /2, and from f2 back to /3. Thus the loop f3-f2-f3 has been found. We return to the last equation found, /2, and see that no other equation feeds it, in which case we must return to the equation found just previous to/2, namely f3. Now/3 is fed by f4 and a new path can be traced to obtain a loop f3-j4-f5-f3. Steward continues this procedure until all of the feeds to each equation have been exhausted, but it is not obvious when this situation occurs except if a tree is drawn of the paths. For a large block, drawing a tree may not prove to be especially feasible. 

In the adjacency matrix a tear is accomplished by removing the nonzero element in the column corresponding to the equation in which the variable is the output and the row corresponding to the equation from which the variable is torn. For example, in Fig. 14 removal of the nonzero element of row 1 and column 5 corresponds to tearing the output variable ofA from/,. When this tear is made there is no longer any information flow directly from fs to /j in the torn block, and loop A (/i,/5) is broken only loops B, C, and D are retained in the torn block. If the element of row 3 and column 4 is torn instead of the element of the first row and fifth column, loop D is broken, and only loops A, B, and C remain in this torn system. 

If an equation appears in more than one loop, one tear can break all of the loops in which the equation appears if in each of these loops the equation included in both loops has exactly the same equation feeding it in the loop. For example, column 2 of the occurrence matrix in Fig. 16a contains nonzero elements in rows 2 and 4. Upon inspection of the corresponding loops, B and D, in the tree of Fig. 15 it is seen that f2 is fed by f3 in both loops (/3 appears immediately after f2 in paths involved in loops B and D). Therefore, loops B and D can be broken by tearing the output variable of f3 from the equation f2. Now instead of putting l s as entries in row i and column j of the occurrence matrix to indicate that equation j appears in loop i, we insert instead the number of the equation that feeds equation j in loop i as in Fig. 16b. Then if the same nonzero number appears more than once in the same column, all of the loops represented by the rows in which that number appears... 

In the residual occurrence matrix comprised solely of independent columns, if a row contains only one nonzero element, the stream corresponding to the column in which the nonzero element appears is the only stream that can be torn to break the loop corresponding to that row. The next step of the algorithm is (1) to remove the columns in which a lone nonzero element in a row appears and (2) to remove all of the rows that have nonzero elements in that column. Each column removed in this step corresponds to tearing the stream represented by the column, and all of the rows removed represent loops that are broken by the tear. 

After all of the rows that contain only one nonzero element are removed from the matrix, the columns that are strictly contained in a set are removed. A column, k, is strictly contained in a set of columns if (1) at least one column in the set contains a nonzero element in each row in which column k also has nonzero entries, and if (2) together, the columns of the set have less variables associated with the streams they represent than does the stream represented by column k. The columns representing streams with the largest number of variables that are strictly contained in the set are removed first, after which the reduced matrix is checked for rows with only one nonzero element. Whenever a row is obtained with only one nonzero element, it is removed and a new tear is performed as before. 

C REAOING. THE MATRIX OUTPUT SET IS ON THE MAIN DIAGONAL. AND THE ROWS C ARE IN THE FINAL PRECEDENCE ORDER. THE ELEMENTS IN A MATRIX ROW ARE CM THOSF VARIABLES ASSOCIATED WITH THE EQUATION GIVEN UNDER THE C COLUMN HEADED EONS. THE COLUMN HEADED VARS. IDENTIFIES THE OUTPUT c VARIABLE FOR THAT EQUATION. BY TRANSPOSING THE VECTOR OF NUMBERS C UNDER THE COLUMN VARS. AND PLACING IT ACROSS THE TQP OF THE MATRIX(X.X) C M YOU CAN IDENTIFY EACH OF THE VARIABLES BY NUMBER. EACH COLUMN WITH C M NONZERO ELEMENTS ABOVE THE MAIN DIAGONAL REPRESENTS AN ITERATED C m VARIABLE. 

C THE NONZERO ELEMENTS OF THE OCCURRENCE MATRIX ARE READ HERE. 

---