Abstract:
A method, system, and data structure are provided which facilitate matrix multiplication with advantageous computational efficiency. The invention, as variously implemented as a processing system, method, or data structure in a recording medium such as a memory, has applicability to numerous fields, including linear programming, where a great deal of multiplication of large, sparse matrices is performed. The method of the invention includes the steps of creating a first submatrix block from non-zero terms of a sparse matrix, such that all of the terms within a given column of the submatrix block are form a respective column of the sparse matrix, creating a corresponding second index submatrix block of the same dimensions as the first block, such that each term of the second block identifies the position of the corresponding term of the first block within the sparse matrix, in terms of a row and column index. Finally, the method includes reordering terms of the first and second blocks correspondingly, as necessary to produce a final configuration within the first and second blocks such that all of the row indices within any given row of the second block are distinct.

Description:
This is a continuation of application Ser. No. 08/367,627 filed on Jan. 3, 1995 now abandoned. 
    
    
     TECHNICAL FIELD 
     The present invention is generally related to the field of matrix processing. More specifically, the invention relates to a system and method for performing matrix multiplication in a manner more computationally efficient than has been done heretofore, the method having particularly advantageous applicability to solving linear programming problems. 
     BACKGROUND OF THE INVENTION 
     As an introduction to the types of issues which arise in the application of processing systems to matrix processing, a discussion of linear programming will be given, including a discussion of what techniques are used for solving linear programming problems and of what role matrix processing plays in those techniques. From this discussion, it will be evident how the method of the invention is applicable to improve matrix processing performance. 
     The field of linear programming came into existence in the years following World War II, in which various types of logistical problems, many extremely complex and involving up to thousands of variables, needed to be solved as cost-efficiently as possible. 
     A typical problem might be one of supplying various types of goods from a number of distribution sites to a number of destinations. Each destination has certain requirements regarding how many of each type of goods it needs to have on hand. For a given type of goods at a given location, a certain cost per unit shipped is associated with each distribution point. Generally, the cost is related to the distance between the distribution point and the destination, or the mode of transportation which must be used in shipping the goods. Also, there may be constraints on the quantity of goods shipped. For instance, a given distribution site might have a limited quantity of a certain type of goods on hand. Thus, a nearby destination having a greater demand for those goods is required to ship some of its requirements from a more distant, more costly, distribution site. Also, since linear programming problems often arise out of &#34;real-world&#34; situations, zero is often a lower bound on the value of a variable. That is, the quantity of goods shipped from a given source to a given destination will likely have zero as a realistic lower bound. 
     The problem, then, is to find values for the quantities of each type of goods shipped from each distribution point to each destination, such that the total cost required for all the shipments is minimized, but all of the destinations are supplied with their requirements of all types of goods. This problem, as with essentially all linear programming problems, is expressed mathematically in the following general form: ##EQU1## subject to: 
     
         Ax=b                                                       (2) 
    
     where 
     
         L.sub.j ≦x.sub.j ≦U.sub.j                    ( 3) 
    
     That is, find a vector of x values such that the sum of products of the x values and a set of coefficients is minimized, given a set of constraints on the x values. 
     The first of these three expressions may be through of as a cost function. In the example given above, the variables x j  represent the quantities of goods shipped, and the variables c j  represent the costs per unit associated with shipping the goods. Thus, each term of the sum is a total cost for shipping one type of goods from one distribution point to one destination. The sum of all such terms is the grand total cost for all shipments. It will be seen, then, that minimizing this grand total cost of all such shipments is the basic objective of a linear programming problem. 
     The constraint Ax=b defines the &#34;ground rules&#34; for the linear programming problem under which the cost is to be minimized. In this expression, b is a vector of constants, in which each constant is the total quantity of one of the types of goods required by the destination. The A matrix and the b vector represent information such as the requirements of each location for each type of goods, etc. Note that Ax=b may also be a set of inequalities, such as Ax≦b, etc. 
     Finally, the last expression represents constraints, if any, on the quantities of goods shipped from a given distribution point. In many linear programming problems, the lower bound L j  is zero. As described above, the upper bound U j  is a constraint, which may limit the maximum value for the quantity of a given type of goods shipped from a given location, if that is all there is on hand at that location. 
     Ax=b represents a system of linear equations, where x is a vector of variables, and A is a two-dimensional array of coefficients. Since A, x, and b are vectors or matrices, it will be seen that the expression Ax=b is s matrix multiplication problem. It will thus be seen that matrix processing capability is fundamental to solving linear programming problems. 
     In practice, the coefficient matrix A is usually sparse. A matrix is said to be &#34;sparse&#34; if a large portion of its terms are zero. 
     Given a system of n equations in n variables, it is possible to solve the system of equations to obtain unique values for the variables, if such unique values exist. However, in most realistic linear programming problems, the number of variables greatly exceeds the number of equations. Thus, there are a large number of possible solutions to such a system of equations. Because of this, it is possible to attempt to find one of the possible solutions which minimizes the total cost. 
     If the variables x j  are visualized as defining an n-dimensional solution space for the linear programming problem, then the range of possible solutions can be represented as an n-dimensional polyhedron within that solution space. Because the equations defined by Ax=b are linear, the faces of the solution polyhedron are planar. Faces of the solution polyhedron are defined by the limiting values of various ones of the variables x j . It can be proven that the minimum cost is given by a solution represented by one of the vertices of the polyhedron. 
     The concept of a solution polyhedron in a solution space is a key to conceptualizing the different strategies for solving linear programming problems, which will now be presented. 
     The Simplex Method 
     The classic text by Dantzig, &#34;Linear Programming and Extensions,&#34; Princeton University Press, Princeton, N.J. (1963), teaches a method, called the &#34;simplex method&#34;, for solving a linear programming problem, i.e., finding values for the vector of x variables such that the cost is minimized. In the simplex method, a solution represented by one of the vertices of the solution polyhedron is selected, more or less at random. Then, moves are made in a sequence from one vertex to another, each move decreasing the total cost, until finally a vertex is reached from which no additional movement can reduce the cost any further. This final vertex is the solution to the linear programming problem. 
     The simplex method is executed as follows: A group of variables equal to the number of equations are selected, more or less at random, and are designated &#34;basic variables.&#34; The remaining variables are called &#34;nonbasic&#34; or &#34;independent&#34; variables. The independent variables are set to feasible values, i.e., values within the range defined by the upper and lower limits given in the above expression. Since the lower limit L j  is often 0, feasibility generally means that the variables have nonnegative values. 
     Using algebraic techniques similar to those used in solving n equations in n variables, i.e., adding linear combinations of the equations, the system of linear equations is placed into &#34;canonical form,&#34; in which each equation has a coefficient 1 for one of the basic variables, and coefficients 0 for all the other basic variables. Thus, placing the equations in canonical form is equivalent to solving for the basic variables. This solution, if it is feasible, represents one of the vertices of the solution polyhedron. 
     Next, a better solution is sought as follows: The value of one of the independent variables is varied. Varying the value of the independent variable has the effect of changing the values of other variables. If varying the independent variable reduces the total cost, that independent variable is varied in value until one of the basic variables reaches a limiting value, such as zero. That basic variable is now replaced by the independent variable whose value had been changed. The values for the resulting new set of basic variables define another vertex of the solution polyhedron, connected to the first vertex by an edge. Varying the value of the independent variable had the effect of moving along an edge of the solution polyhedron which runs from the first vertex to the new vertex. 
     The process just described is repeated, moving from vertex to vertex, until no further change to any of the independent variables results in a cost reduction. At this point, the values of the basic and independent variables define the optimal solution to the linear programming problem, and the simplex method has been completed. 
     Since there are often on the order of thousands of variables in a realistic linear programming problem, solutions are typically calculated on computers. Because of the large numbers of calculations involved in matrix algebra, and the large number of iterations required for a technique such as the simplex method, computational efficiency is an important objective in a computer-implemented linear programming solver. 
     In particular, an implementation of the simplex method involves certain specific types of matrix calculations. First, in the expression Ax=b, Ax is broken up into two terms, i.e., two matrix products, representing basic variables x b  and independent variables x n , as follows: 
     
         Ax=Bx.sub.b +Nx.sub.n =b                                   (4) 
    
     This expression is then solved for x b  as follows: 
     
         x.sub.b =B.sup.-1 b-B.sup.-1 Nx.sub.n                      ( 5) 
    
     The cost z associated with the selected values for the variables is given by 
     
         z=c.sup.T.sub.B x.sub.B +C.sup.T.sub.N x.sub.N             ( 6) 
    
     It is necessary to use the matrix transposes c T   b  and c T   n  of the basic and independent portions of the cost coefficient matrix for these matrix multiplication expressions to be in proper form. Therefore, a cost differential d j  which is associated with changing the value of one of the independent variables associated with the j-th column of the N matrix is given by the expression 
     
         d.sub.j =c.sub.j -c.sup.T.sub.B B.sup.-1 a.sub.j           ( 7) 
    
     where c j  is the cost, absent the change of value of the independent variable, a j  is the j-th column of N, and B -1  is the inverse matrix of B. For a change of value of an independent variable to produce an overall reduction in cost, d j  should have a value less than zero. 
     The above expression is calculated many times during the course of solving a linear programming problem. Therefore, the matrix product c T   B  B -1 , which is a one-dimensional vector, is designated as π T , and referred to as the &#34;shadow prices&#34; or &#34;pi values.&#34; During the course of the simplex method, the matrix product π T  A, or π T  a j  for individual columns of the matrix A, is calculated many times. The expression π T  A is referred to as &#34;multiplication on the left,&#34; referring to the position of the matrix π T  to be multiplied with the coefficient matrix A. This calculation is made for every iteration of the simplex method, to determine whether the change in value of an independent variable is reducing the total cost. For these calculations, which may number in the thousands, A remains constant, but the pi values change as different variables are swapped in and out of the set of basic variables. 
     A different matrix calculation is made, following each iteration, to check for the feasibility of the solution. The vector of solutions x is multiplied by the coefficient matrix, to evaluate Ax=b. This is referred to as &#34;multiplication on the right,&#34; again referring to the position of the vector to be multiplied with the coefficient matrix A. In the simplex method, multiplication on the right is executed much less frequently than multiplication on the left. Accordingly, in vector processing implementations of linear programming software, optimization for multiplication on the left has produced good computational efficiency for the simplex method. While this optimization decreases the efficiency of multiplication on the right, overall computational efficiency is not greatly reduced, since multiplication on the right is performed relatively infrequently. 
     Interior Point Methods 
     More recently, alternative methods for solving linear programming problems have been explored. These other methods have been referred to as &#34;interior point&#34; methods, because they can be characterized as moving through the interior of the solution polyhedron. This is in contrast with the simplex method, in which motion is only along the outer edges of the solution polyhedron. 
     Several different interior point methods are discussed in detail in Forrest and Tomlin, &#34;Implementing Interior Point Linear Programming Methods in the Optimization Subroutine Library,&#34; IBM Systems Journal, Vol. 31, No. 1, 1992. One class of interior point methods, for instance, is called barrier methods. In a barrier method, non-linearities are introduced which prevent the limits from being violated. Then, calculus-based methods are used for the minimization. For example, in a logarithmic barrier method, the problem is to find values for the variables x j  which minimize ##EQU2## subject to: 
     
         Ax=b                                                       (9) 
    
     where 
     
         L.sub.j ≦x.sub.j ≦U.sub.j                    ( 10) 
    
     In the above expressions, μ→0 and μ&gt;0. Because μ is positive, the logarithm terms become large as the variable approaches the limit. However, since μ tends toward zero, the logarithm terms are small, and do not greatly change the result from what it would be if only the cost terms were summed. Since the logarithmic terms of the sum are not defined for values outside the upper and lower limiting values, the bounds cannot be violated. 
     In essence, solving such a problem involves taking a series of steps from an initially selected solution, each step having a given step length, and each step being taken in a direction, through the solution polyhedron, of reduced cost. The major computational burden of each step of the interior point method is a gradient projection, which is solved as a least-squares problem. The solution of the least-squares problem is a vector change. For the least-squares solution, pi values and reduced costs are updated in a manner similar to that described in connection with the simplex method. 
     In particular, the least-squares calculation involves multiplication on the right. The matrix product Ax is computed a much greater number of times in interior point methods than in the simplex method. 
     Considerations that Affect Computational Efficiency 
     From the foregoing, it will be seen that, whether the simplex method or an interior point method is used to solve a linear programming problem, there will be a great many matrix multiplications involving the coefficient matrix A. Matrix multiplication is generally implemented on a processor having vector processing capability as vector multiplication of rows and/or columns. Multiplications both on the left and on the right are used. Frequently, the A matrix is sparse, i.e., a large number of the terms of the A matrix have the value zero. Thus, computational efficiency is improved by reducing the number of multiplications involving zero terms. 
     In Forrest and Tomlin, &#34;Vector Processing in Simplex and Interior Methods for Linear Programming&#34;, 22 Annals of Operations Research 71-100 (1990) 2!, a method is employed for storing coefficients in computer memory for convenient access and efficient execution of multiplication on the left. Columns of the A matrix having large numbers of non-zero terms are stored separately for vectorization. Columns having relatively few non-zero terms are stored in blocks. A second block of memory contains indices, each index corresponding with one of the non-zero terms stored in the block, and indicating which position in the column of the A matrix the term occupied. The cost reduction is then calculated, using a vector processor, by reading a vector of indices from the second block, obtaining a vector of pi values, selecting each pi value for the vector based on the value of the corresponding index. Finally, the scalar product of the pi value vector and the corresponding row of the first block is added to a cost reduction value. This process is repeated for each row of the first block. Because this method involves multiplying rows of the A matrix terms, computational efficiency is achieved by storing the terms in memory row-wise. 
     Since the most frequently executed matrix multiplication in the simplex method is that on the left, the above data structure works well. However, since the advent of interior point methods, it has been common practice to follow interior point optimization by iterations of the simplex (or a simplex-like) method. For the newer interior point methods, where multiplication on the right (Ax) takes place more frequently, the above data structure is not well suited. Therefore, to accommodate the newer interior point methods, it is desirable to find a way of utilizing the above-described data structure efficiently to vectorize multiplication on the right. 
     SUMMARY OF THE INVENTION 
     It is therefore an object of the invention to provide a processing system and method which efficiently performs multiplications on the right, using data structures containing coefficients of the A matrix, stored in a manner conducive to multiplication on the left. 
     To achieve these and other objectives, there is provided in accordance with the invention, a method for facilitating efficient matrix processing by substantially eliminating zero-product terms. The method permits multiplication on the left, as described above, but also advantageously allows for correct multiplication on the right. 
     The method of the invention includes the steps of creating a first submatrix block from non-zero terms of a sparse matrix, such that all of the terms within a given column of the submatrix block are from a respective column of the sparse matrix, creating a corresponding second index submatrix block of the same dimensions as the first block, such that each term of the second block identifies the position of the corresponding term of the first block within the sparse matrix, in terms of a row and column index. Finally, the method includes reordering terms of the first and second blocks correspondingly, as necessary to produce a final configuration within the first and second blocks such that all of the row indices within any given row of the second block are distinct. 
     While the invention is primarily disclosed as a method, it will be understood by a person of ordinary skill in the art that an apparatus, such as a conventional data processor, such as that shown in FIG. 12, including a CPU, (central processing unit) 1202 memory 1204, I/O (input/output) 1206 program storage 1208, a connecting bus 1210, and other appropriate components, could be programmed or otherwise designed to facilitate the practice of the method of the invention. Such a processor would include appropriate program means stored in the program storage 1208, for executing the method of the invention. Also, an article of manufacture, such as a pre-recorded disk or other similar computer program product, for use with a data processing system, could include a storage medium and program means recorded thereon for directing the data processing system to facilitate the practice of the method of the invention. It will be understood that such apparatus and articles of manufacture also fall within the spirit and scope of the invention. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is an example of a sparse matrix with regard to which the method of the invention is to be applied. 
     FIG. 2 is a matrix of non-zero terms of the matrix of FIG. 1 which is used pursuant to the method of the invention. 
     FIG. 3 is a matrix of indices, the matrix being equal in numbers of rows and columns to that of FIG. 2, each index having two subscripts whose values give the row and column numbers, respectively, of the positions within the matrix of FIG. 1 from which the corresponding terms of FIG. 2 are taken. 
     FIG. 4 is a flowchart showing the method in accordance with the invention. 
     FIGS. 5 and 6 are processed portions of the matrix of indices of FIG. 3, showing the state of the matrix of indices before and after a first intermediate step of the method of the invention. 
     FIG. 7 is the matrix of non-zero terms from FIG. 2, as modified as of a point in time contemporaneous with FIG. 6. 
     FIGS. 8 and 9 are processed portions of the matrix of indices of FIG. 3, showing the state of the matrix of indices before and after a second intermediate step, subsequent to the first intermediate step, of the method of the invention. 
     FIG. 10 is the matrix of non-zero terms from FIG. 2, as modified as of a point in time contemporaneous with FIG. 9. 
     FIG. 11 is a flowchart showing an additional aspect of the method of the invention. 
     FIG. 12 is a system block diagram of a processing system according to the invention. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     First, the method of the invention will be explained in a general sense through reference to a sparse coefficient matrix (FIG. 1), a block of non-zero terms from the coefficient matrix (FIG. 2), and a corresponding block of indices (FIG. 3). Then, a preferred embodiment of the invention will be discussed in detail. 
     FIG. 1 is a 10-by-10 matrix of integers, which will be used as an example for describing the invention. While A matrices in real linear programming problems are of the order of thousands-by-thousands in size, 10-by-10 is a convenient size for illustrative purposes. For reference purposes, the columns are numbered 1 through 10 from left to right, and the rows are numbers 1 through 10 from top to bottom (row and column numbers are not shown in FIG. 1). Note that the A matrix of FIG. 1 is relatively sparse, in that only 33 of its 100 terms have non-zero values. 
     In a typical multiplication on the left pursuant to the simplex method, in which equation (7) is being evaluated, a π T  vector of pi values is multiplied by the A matrix of FIG. 1, and all of the product terms are summed. Specifically, the simplex method calculates equation (7) by multiplying each non-zero term of the matrix A by the term of the π T  vector of pi values which corresponds with the column in which the A matrix term appeared. 
     Multiplication involving a sparse matrix involves a large number of zero products produced by, which can be eliminated to improve computational efficiency. To achieve this increased computational efficiency for multiplication on the left, submatrices, or &#34;blocks,&#34; are produced which have subsets of the terms of the A matrix. In particular, the A matrix is examined for columns which all have the same number of non-zero terms, and those non-zero terms are blocked together. In this case, columns 1, 3, 5, 6, and 8 each have four non-zero terms. Accordingly, a 4-by-5 block, shown in FIG. 2, is created by grouping the four non-zero terms of each of these five columns. 
     In order to correctly multiply the appropriate pi values with these non-zero terms, the mapping of π T  vector terms with submatrix terms must take into account that the number of A matrix terms in a row of the submatrix is less than the number of terms in the λ T  vector. This is done by constructing a companion block, shown in FIG. 3, which has a row and column index for each term in the FIG. 2 submatrix. Each term of the row and column index matrix of FIG. 3 indicates, for a given column of the A matrix, the row and column of the A matrix in which the non-zero term appears. The particular way in which the row and column indices are given for each term of the index block of FIG. 3 may be chosen based on suitability for the particular application. For the discussion which follows, the terms of the index block of FIG. 3 will be referred to generically as index terms, but it will be understood that each index term includes a row index and a column index. 
     A matrix processor makes use of this data structure, during execution of a π T  A (multiplication on the left) calculation in the simplex method, by using an appropriate technique, such as indirect addressing, to determine which pi values are to be read and multiplied by the non-zero terms in the FIG. 2 block, and which pi values can be ignored. In the example given in FIGS. 1-3, the first, third, fifth, sixth, and eighth terms of the π T  vector are indirectly addressed, using the indices of FIG. 3, so that the appropriate products of pi values and A matrix terms are computed for use in equation (7). Note that, while the indices of FIG. 3 are both row and column indices, only the column index matters for multiplication on the left, because the same term of the π T  vector is multiplied by all of the non-zero terms in the column of the A matrix which corresponds with that π T  vector term. 
     As discussed above, this scheme works well for the simplex method, which performs many multiplications on the left, and relatively few multiplications n the right. For optimization in a computer having matrix processing capability, the blocks of A matrix coefficients and the accompanying blocks of indices for indirect addressing of the pi values should be stored row-wise. As a practical consideration, it is also useful to limit the number of columns in such a block to the length of the vector registers of the particular machine on which the calculation is being run. For instance, if the vector register length were four, then the first four columns of FIGS. 2 and 3 could be set up as one pair of blocks, and the fifth column of FIGS. 2 and 3 would be treated as separate blocks. 
     Let us now consider how well adapted this scheme is for multiplication on the right. The multiplication on the right used in interior point schemes, Ax, can be converted to a multiplication on the left by taking the transposes of the A matrix and the x vector. That is, Ax is equivalent to x T  A T . However, for vector processing, the terms in a given row of A are stored adjacent to each other, while the terms of a given column need not be so. For A T , however, just the opposite is true: the terms of a given column of A are now in the same row of A T , and therefore should be stored adjacent to each other. The result is that A T  must be stored separately from A. This duplication of the stored terms of the A matrix is an undesirable use of storage space. 
     The submatrices discussed above in connection with multiplication on the left should be used as well for multiplication on the right, if possible. However, there is a problem. If the row indices in a given row of FIG. 3 are not distinct, the procedure leads to indeterminate (but certainly incorrect) results. However, if the row indices corresponding with each row of the block are distinct, the procedure works. 
     Therefore, in accordance with the invention, a method is presented for arranging for the indices corresponding with each row of the block to be distinct as often as possible. 
     The method of the invention is possible because, regardless of the order of the terms within any given column of FIG. 2, the π T  A multiplication on the left gives the same result. Therefore, in accordance with the invention, it is possible to rearrange the order of terms in a given column to facilitate the distinctness condition required for the Ax multiplication on the right. 
     In accordance with the invention, the elements within each column of FIG. 2 are reordered as necessary to maximize the number of rows of the block in FIG. 2 whose row indices in FIG. 3 are distinct. It can be shown that the entries in an s by z block can be re-ordered within each column in such a way that each row of the block has entries whose row indices are distinct if and only if no row entry appears more than s times in the block. 
     In a preferred embodiment of the invention, the reordering of the terms of the blocks is performed according to an algorithm, given in flowchart form in FIG. 4. 
     In FIG. 4, the preferred embodiment of the method includes processing the terms of the blocks of coefficient matrix terms and corresponding indices one term at a time. The first term to be processed is the term in the first row and the first column. The remaining terms in the first column are processed, one by one. Then the terms in the next column are processed, and so on, until the terms in the last column are processed. 
     In FIG. 4, the variables k and j are used to represent the row number and the column number, respectively, of the term being processed. The variables j and k are initialized in steps 2 and 4 of the flowchart. A standard process, which will be readily understood by a skilled programmer, is used for incrementing the row number k through the first column, reinitializing k and incrementing j to the next column, and testing for the end of a column and for the last column. The group of blocks collectively designated 6 shows these steps. 
     The objective of the flowchart is to ensure that none of the rows of the index array have the same index value occurring more than once. This objective is achievable as long as the number of occurrences of any given index value in the index array is less than or equal to the number of rows of the index array. The essence of the method, then, is to check each index value to see whether it matches any indices already checked in the same row, and, if so, to swap that index with another index, further down the same column, which does not match any indices already checked in the same row. In the detailed discussion which follows, the term &#34;processed part&#34; will be used to refer to the terms within a row, column, or the entire array which have already been checked using the method to be described. 
     Step 8 is a test, in which it is determined whether i kj , the index for the term currently being tested, matches any previously checked indices in that row. That is, it is checked whether there is any i ka , where 1≦a&lt;j, which equals i kj . If not, the flowchart proceeds to step 6 to move to the next term. 
     If there is a matching index, then it is necessary to swap that index with another index farther down the same column of the index block, and to swap the corresponding terms of the coefficient block (FIG. 2). However, the index to be swapped into the k-th row/j-th column position of the block must not equal any index in the processed part of the same row. 
     Thus, step 10 checks the indices i bj , where k&lt;b≦s, to find one which does not match any of the indices i kc , where 1≦c&lt;j. If step 10 finds such an index, then in step 12, the two indices are swapped. Then, the index being checked is incremented in step 6, and the method moves on to the next index to be checked. 
     However, it will sometimes be the case that there is no such non-matching index below i kj . Then, it becomes necessary to swap, instead, one of the indices j kc  elsewhere in the processed part of row k. Step 14 describes such a case, where the current index, i kj , has the same value, v, as an already processed index i kh  in the same row k. In step 16, the processed part of the array is searched to find a row which does not contain an index of value v. Let us say that row 1 has no indices of value v it is processed part. The index i lh , in the same column h as the index i kh  has a value v&#39;. Thus, i lh  will be swapped with i kh . This is done in step 18. After this swap, rows k and h each contain one index of value v. 
     However, it is possible that row k might contain another index of value v&#39;. If this is the case, a further swap must be made to eliminate this duplication of index values within the same row. Thus, step 20 checks whether any other indices in row k match the value v&#39;, which was swapped into row k from row l in step 18. If no other index of value v&#39; is found in the processed part of row k, then the process proceeds to step 6, to move on to the next index. 
     If another index i kh , of value v&#39; is found in the processed part of row k at column h&#39; (step 22), then the method proceeds to step 24. Since essentially the same swapping procedure will be used to separate the two indices of value v&#39; in row k, the flowchart uses steps 14, 16, 18, and 20 as described above. Step 24 facilitates this use of the previously described steps in software, by replacing the value v with v&#39;, and by replacing the column of the index to be swapped, column h, with column h&#39;. As long as the number of occurrences of any given index value does not exceed the number of rows in the array, eventually step 20 will test for a situation where the index value swapped into row k does not match any other indices already in row k. Then, the method proceeds to step 6 to move on to the next index in the array. 
     The method then proceeds until all indices have been checked. The final result is a reordered block of A matrix coefficients and a corresponding block of indices, where, within each row, all of the row indices are distinct. 
     Consider, as an example, how the method of the invention processes the submatrix of FIG. 2 and the corresponding block of indices given in FIG. 3. FIG. 5 shows an intermediate state in the processing of FIG. 3, in which only the processed part is shown. The top index of the third column, i 2 ,5, has the same row index, 2, as the top index of the second column, i 2 ,3. Therefore, step 10 finds an index in the third column whose row index is different from any row indices already in the top row. The second index down in the third column is i 4 ,5, whose row index, 4, does not match either of the two processed indices in the top row, i 3 ,1 and i 2 ,3. Therefore, the top two indices in the third column are swapped by step 12. The processed part of the index block now appears as in FIG. 6. Likewise, the A matrix terms are swapped, and FIG. 2 is converted to FIG. 7. 
     FIG. 8 illustrates the processed part of the index submatrix when the bottom index in the third column, i 10 ,5, is being processed. Here, the row index matches that of the bottom index of the second column. However, this time step 10 is unable to find another index below this one, because there aren&#39;t any more in the third column. Thus, processing proceeds to step 14, which identifies the bottom index of the second column as having the same row index. Step 16 looks through the second column to find an index whose row index does not appear in the bottom column. The top index of the second column, i 2 ,3, satisfies this criterion. Thus, step 18 swaps the top and bottom indices of the second column. The result is as appears in FIG. 9. Also, the corresponding A matrix terms are swapped, and the result is as shown in FIG. 10. 
     In summary, the method of the invention rearranges indices, and corresponding terms, within the arrays so that multiplication on both the right and on the left can be vector processed. As a consequence, the invention provides advantageously enhances efficiency of memory consumption, and also vector processing efficiency. The method according to the invention can be implemented so as to have a worst case performance of O(sz 2 ) for blocks of s rows and z columns. In practice, less time than this is generally required for processing the blocks. 
     It will sometimes be the case that the above conditions are not satisfied, that is, a given row index might occur more than s times for an s by z block. This situation may be dealt with as shown in the flowchart of FIG. 11. When this condition is detected (step 30), occurrences of a frequently occurring row index are swapped to a given row, such as the bottom row, of the block (step 32). That row is then removed from the block (that is, the number of rows is reduced, say, from s to s-1, as shown in step 34). For processing purposes, the value of s may be changed to reflect that the number of rows has been reduced (step 36). If there is now another row index which appears more than s times (s having been reduced in value), the test of step 30 causes the process to be repeated. If and when the block, reduced by removing one or more bottom rows, eventually satisfies the criterion that no row index occurs more frequently than the number of rows remaining in the block, then the vectorized multiplication on the right may take place as shown in FIG. 4 (represented schematically as step 38 in FIG. 11), and the stripped-off row or rows are processed separately (step 40). Of course, the block of A matrix terms (such as FIG. 2) is processed accordingly. 
     Experimental runs of vectorized calculations using the reordering method of the invention have produced reductions on the processing time for an Ax multiplication on the right up to approximately 50%. The reordering method according to the invention has been found to be fast enough that, even where relatively little improvement in the Ax calculation time has been realized, the improvement more than compensates for the reordering time. 
     Those skilled in the art will recognize that the foregoing description has been presented for the purposes of illustration and description only. It is not intended to be exhaustive or to limit the invention to the precise forms disclosed, and obviously many modifications and variations are possible in light of the above teachings. 
     Therefore, the embodiments set forth herein are presented in order to best explain the principles of the present invention and its practical applications to thereby enable others skilled in the art to best utilize the present invention in various embodiments, modifications, and equivalents as are suited to the particular use contemplated.