US2002161812A1PendingUtilityA1

Computer product and method for sparse matrices

39
Priority: Oct 30, 1998Filed: Nov 7, 2001Published: Oct 31, 2002
Est. expiryOct 30, 2018(expired)· nominal 20-yr term from priority
Inventors:Gautam DoshiRoger GolliverBob Norin
G06F 17/16
39
PatentIndex Score
0
Cited by
0
References
0
Claims

Abstract

A computer program product and method for multiplying a sparse matrix by a vector are disclosed. The computer program product includes a computer readable medium for storing instructions, which, when executed by a computer, cause the computer to efficiently multiply a sparse matrix by a vector, and produce a resulting vector. The computer is made to create a first array containing the non-zero elements of the sparse matrix, and a second array containing the end_of_row position of the last non-zero element in each row of the sparse matrix. A variable is initialized, and then, for each row of the second array, the computer is made to do one of two things. Either, it equates the variable to the sum of the variable and the product of a particular element of the first array and a particular element of the vector. Or, it equates a particular element of the resulting vector to the variable, and then equates the variable to a particular value.

Claims

exact text as granted — not AI-modified
What is claimed:  
     
         1 . A computer readable medium for storing instructions which, when executed by a computer, cause the computer to multiply a sparse matrix by a vector and produce a resulting vector, by performing the steps of: 
 creating a first array of elements containing the non-zero elements of the sparse matrix;    creating a second array of elements containing the row position of the last non-zero element in each row of the sparse matrix;    initializing a variable; and 
 executing a set of instructions for each element of the first array, either equating the variable to the sum of the variable and the product of the element of the first array and a particular element of the vector, or equating a particular element of the resulting vector to the variable, and then equating the variable to a particular value.  
   
     
     
         2 . The computer readable medium of  claim 1  wherein the set of instructions is predicated.  
     
     
         3 . The computer readable medium of  claim 1  wherein the particular value is the product of the element of the first array and the particular element of the vector.  
     
     
         4 . The computer readable medium of  claim 1  further comprising the step of prefetching the elements of the first array from memory.  
     
     
         5 . The computer readable medium of  claim 1  further comprising an allocation control mechanism wherein the allocation control mechanism separates the elements with temporal locality from the elements with spatial locality.  
     
     
         6 . The computer readable medium of  claim 1  further comprising the step of storing the elements with temporal locality in a cache memory.  
     
     
         7 . The computer readable medium of  claim 1  further comprising the step of striding through the elements with spatial locality.  
     
     
         8 . The computer readable medium of  claim 1  wherein the elements of the first array maintain spatial locality.  
     
     
         9 . The computer readable medium of  claim 1  wherein the elements of the vector maintain temporal locality.  
     
     
         10 . A method for causing a computer to multiply a sparse matrix by a vector and produce a resulting vector, comprising the steps of: 
 creating a first array of elements containing the non-zero elements of the sparse matrix;    creating a second array of elements containing the row position of the last non-zero element in each row of the sparse matrix;    initializing a variable; and 
 executing a set of instructions for each element of the first array, either equating the variable to the sum of the variable and the product of the element of the first array and a particular element of the vector, or equating a particular element of the resulting vector to the variable, and then equating the variable to a particular value.  
   
     
     
         11 . The method of  claim 10  wherein the set of instructions is predicated.  
     
     
         12 . The method of  claim 10  wherein the particular value is the product of the element of the first array and the particular element of the vector.  
     
     
         13 . The method of  claim 10  further comprising the step of prefetching the elements of the first array from memory.  
     
     
         14 . The method of  claim 10  further comprising an allocation control mechanism wherein the allocation control mechanism separates the elements with temporal locality from the elements with spatial locality.  
     
     
         15 . The method of  claim 10  further comprising the step of storing the elements with temporal locality in a cache memory.  
     
     
         16 . The method of  claim 10  further comprising the step of striding through the elements with spatial locality.  
     
     
         17 . The method of  claim 10  wherein the elements of the first array maintain spatial locality.  
     
     
         18 . The method of  claim 10  wherein the elements of the vector maintain temporal locality.  
     
     
         19 . A computer system, comprising a microprocessor and a medium containing instructions, wherein the instructions, when executed by a computer, cause the computer to multiply a sparse matrix by a vector and produce a resulting vector, by performing the steps of: 
 creating a first array of elements containing the non-zero elements of the sparse matrix;    creating a second array of elements containing the row position of the last non-zero element in each row of the sparse matrix;    initializing a variable; and 
 executing a set of instructions for each element of the first array, either equating the variable to the sum of the variable and the product of the element of the first array and a particular element of the vector, or equating a particular element of the resulting vector to the variable, and then equating the variable to a particular value.  
   
     
     
         20 . The computer system of  claim 19  wherein the set of instructions is predicated.  
     
     
         21 . The computer system of  claim 19  wherein the particular value is the product of the element of the first array and the particular element of the vector.  
     
     
         22 . The computer system of  claim 19  further comprising the step of prefetching the elements of the first array from memory.  
     
     
         23 . The computer system of  claim 19  further comprising an allocation control mechanism wherein the allocation control mechanism separates the elements with temporal locality from the elements with spatial locality.  
     
     
         24 . The computer system of  claim 19  further comprising the step of storing the elements with temporal locality in a cache memory.  
     
     
         25 . The computer system of  claim 19  further comprising the step of striding through the elements with spatial locality.  
     
     
         26 . The computer system of  claim 19  wherein the elements of the first array maintain spatial locality.  
     
     
         27 . The computer system of  claim 19  wherein the elements of the vector maintain temporal locality.  
     
     
         28 . A computer readable medium for storing instructions which, when executed by a computer, causes the computer to multiply a matrix having rows and columns containing non-zero elements and zero elements by a vector and produce a resulting vector, by performing the steps of: 
 creating a first array of elements containing the non-zero elements of the matrix;    creating a second array of elements containing the row position of the last non-zero element in each row of the matrix;    creating a third array of elements containing the column position of each non-zero element of the matrix;    initializing a first variable;    initializing a second variable;    executing a set of instructions for an index incremented from 1 to the last element of the second array, in increments of 1, equating a third variable to the product of the element of the first array corresponding to the index, and    the element of the vector corresponding to the element of the third array corresponding to the index;    if the index is less than or equal to the element of the second array corresponding to the first variable, equating the second variable to the sum of the second variable and the third variable;    if the index is greater than the element of the second array corresponding to the first variable, equating the element of the resulting vector corresponding to the first variable to the second variable, incrementing the first variable by 1, and    equating the second variable to a particular value.    
     
     
         29 . The computer readable medium of  claim 28  wherein the set of instructions is predicated.  
     
     
         30 . The computer readable medium of  claim 28  further comprising the step of prefetching the elements of the first array and the elements of the third array from memory.  
     
     
         31 . The computer readable medium of  claim 28  further comprising an allocation control mechanism wherein the allocation control mechanism separates the elements with temporal locality from the elements with spatial locality.  
     
     
         32 . The computer readable medium of  claim 28  further comprising the step of storing the elements with temporal locality in a cache memory.  
     
     
         33 . The computer readable medium of  claim 28  further comprising the step of striding through the elements with spatial locality.  
     
     
         34 . The computer readable medium of  claim 28  wherein the elements of the first array and the elements of the third array maintain spatial locality.  
     
     
         35 . The computer readable medium of  claim 28  where in the elements of the vector maintain temporal locality.  
     
     
         36 . The computer readable medium of  claim 28  wherein the particular value is the product of the element of the first array corresponding to the index, and 
 the element of the vector corresponding to the element of the third array corresponding to the index.  
 
     
     
         37 . The computer readable medium of  claim 28  further including instructions which, when executed by the computer, cause the computer to perform the steps of: 
 storing at least a portion of the vector in a first memory; and  
 storing the first array and/or the second array and/or the third array in a second memory.  
 
     
     
         38 . The computer readable medium of  claim 37  wherein the step of storing in a first memory includes storing in a cache memory.  
     
     
         39 . The computer readable medium of  claim 37  further including instructions which, when executed by the computer, cause the computer to perform the steps of: 
 accessing the vector stored in the first memory via a first access path; and  
 accessing the first array and/or the second array and/or the third array stored in the second memory via an access path different from said first access path.  
 
     
     
         40 . A method for causing a computer to multiply a matrix having rows and columns containing non-zero elements and zero elements by a vector and produce a resulting vector, comprising the steps of: 
 creating a first array of elements containing the non-zero elements of the matrix;    creating a second array of elements containing the row position of the last non-zero element in each row of the matrix;    creating a third array of elements containing the column position of each non-zero element of the matrix;    initializing a first variable;    initializing a second variable;    executing a set of instructions for an index incremented from 1 to the last element of the second array, in increments of 1, equating a third variable to the product of the element of the first array corresponding to the index, and    the element of the vector corresponding to the element of the third array corresponding to the index;    if the index is less than or equal to the element of the second array corresponding to the first variable, equating the second variable to the sum of the second variable and the third variable;    if the index is greater than the element of the second array corresponding to the first variable, equating the element of the resulting vector corresponding to the first variable to the second variable, incrementing the first variable by 1, and    equating the second variable to a particular value.    
     
     
         41 . The method of  claim 40  wherein the set of instructions is predicated.  
     
     
         42 . The method of  claim 40  further comprising the step of prefetching the elements of the first array and the elements of the third array from memory.  
     
     
         43 . The method of  claim 40  further comprising an allocation control mechanism wherein the allocation control mechanism separates the elements with temporal locality from the elements with spatial locality.  
     
     
         44 . The method of  claim 40  further comprising the step of storing the elements with temporal locality in a cache memory.  
     
     
         45 . The method of  claim 40  further comprising the step of striding through the elements with spatial locality.  
     
     
         46 . The method of  claim 40  wherein the elements of the first array and the elements of the third array maintain spatial locality.  
     
     
         47 . The method of  claim 40  wherein the elements of the vector maintain temporal locality.  
     
     
         48 . The method of  claim 40  where in the particular value is the product of the element of the first array corresponding to the index, and 
 the element of the vector corresponding to the element of the third array corresponding to the index.  
 
     
     
         49 . The method of  claim 40  further comprising the steps of: 
 storing at least a portion of the vector in a first memory; and  
 storing the first array and/or the second array and/or the third array in a second memory.  
 
     
     
         50 . The method of  claim 49  wherein the step of storing in a first memory includes storing in a cache memory.  
     
     
         51 . The method of  claim 49  further comprising the steps of: 
 accessing the vector stored in the first memory via a first access path; and  
 accessing the first array and/or the second array and/or the third array stored in the second memory via an access path different from said first access path.  
 
     
     
         52 . A computer system, comprising a microprocessor and a medium containing instructions, wherein the instructions, when executed by a computer, cause the computer to multiply a matrix having rows and columns containing non-zero elements and zero elements by a vector and produce a resulting vector, by performing the steps of: 
 creating a first array of elements containing the non-zero elements of the matrix;    creating a second array of elements containing the row position of the last non-zero element in each row of the matrix;    creating a third array of elements containing the column position of each non-zero element of the matrix;    initializing a first variable;    initializing a second variable;    executing a set of instructions for an index incremented from 1 to the last element of the second array, in increments of 1, equating a third variable to the product of the element of the first array corresponding to the index, and    the element of the vector corresponding to the element of the third array corresponding to the index;    if the index is less than or equal to the element of the second array corresponding to the first variable, equating the second variable to the sum of the second variable and the third variable;    if the index is greater than the element of the second array corresponding to the first variable, equating the element of the resulting vector corresponding to the first variable to the second variable, incrementing the first variable by 1, and    equating the second variable to a particular value.    
     
     
         53 . The computer system of  claim 52  wherein the set of instructions is predicated.  
     
     
         54 . The computer system of  claim 52  further comprising the step of prefetching the elements of the first array and the elements of the third array from memory.  
     
     
         55 . The computer system of  claim 52  further comprising an allocation control mechanism wherein the allocation control mechanism separates the elements with temporal locality from the elements with spatial locality.  
     
     
         56 . The computer system of  claim 52  further comprising the step of storing the elements with temporal locality in a cache memory.  
     
     
         57 . The computer system of  claim 52  further comprising the step of striding through the elements with spatial locality.  
     
     
         58 . The computer system of  claim 52  wherein the elements of the first array and the elements of the third array maintain spatial locality.  
     
     
         59 . The computer system of  claim 52  wherein the elements of the vector maintain temporal locality.  
     
     
         60 . The computer system of  claim 52  wherein the particular value is the product of the element of the first array corresponding to the index, and 
 the element of the vector corresponding to the element of the third array corresponding to the index.  
 
     
     
         61 . The computer system of  claim 52  further including instructions which, when executed by the computer, cause the computer to perform the steps of: 
 storing at least a portion of the vector in a first memory; and  
 storing the first array and/or the second array and/or the third array are stored in a second memory.  
 
     
     
         62 . The computer system of  claim 61  wherein the step of storing in a first memory includes storing in a cache memory.  
     
     
         63 . The computer system of  claim 61  wherein: 
 the vector stored in the first memory is accessed via a first access path; and  
 the first array and/or the second array and/or the third array stored in the second memory is accessed via an access path different from said first access path.  
 
     
     
         64 . A computer readable medium for storing instructions which, when executed by a computer, cause the computer to multiply a matrix having m rows and n columns containing non-zero elements and zero elements by an initial array having n rows and p columns and produce a resulting array having m rows and p columns, by performing the steps of: 
 creating a first array of elements containing the non-zero elements of the matrix;    creating a second array of elements containing the row position of the last non-zero element in each row of the matrix;    creating a third array of elements containing the column position of each non-zero element of the matrix;    executing a set of instructions for each column of the initial array and the resulting array, incremented from 1 to p in increments of 1, initializing a first variable;    initializing a second variable;    for an index incremented from 1 to the last element of the second array, in increments of 1, equating a third variable to the product of the element of the first array corresponding to the index, and the element of the initial array corresponding to the element of the third array corresponding to the index;    if the index is less than or equal to the element of the second array corresponding to the first variable, equating the second variable to the sum of the second variable and the third variable;    if the index is greater than the element of the second array corresponding to the first variable, equating the element of the resulting array corresponding to the first variable to the second variable, incrementing the first variable by 1, and equating the second variable to a particular value.    
     
     
         65 . The computer readable medium of  claim 64  wherein the set of instructions is predicated.  
     
     
         66 . The computer readable medium of  claim 64  further comprising the step of prefetching the elements of the first array and the elements of the third array from memory.  
     
     
         67 . The computer readable medium of  claim 64  further comprising an allocation control mechanism wherein the allocation control mechanism separates the elements with temporal locality from the elements with spatial locality.  
     
     
         68 . The computer readable medium of  claim 64  further comprising the step of storing the elements with temporal locality in a cache memory.  
     
     
         69 . The computer readable medium of  claim 64  further comprising the step of striding through the elements with spatial locality.  
     
     
         70 . The computer readable medium of  claim 64  wherein the elements of the first array and the elements of the third array maintain spatial locality.  
     
     
         71 . The computer readable medium of  claim 64  wherein the elements of the initial array maintain temporal locality.  
     
     
         72 . The computer readable medium of  claim 64  wherein p is greater than 1.  
     
     
         73 . A method for causing a computer to multiply a matrix having m rows and n columns containing non-zero elements and zero elements by an initial array having n rows and p columns and produce a resulting array having m rows and p columns, comprising the steps of: 
 creating a first array of elements containing the non-zero elements of the matrix;    creating a second array of elements containing the row position of the last non-zero element in each row of the matrix;    creating a third array of elements containing the column position of each non-zero element of the matrix;    executing a set of instructions for each column of the initial array and the resulting array, incremented from 1 top in increments of 1, initializing a first variable;    initializing a second variable;    for an index incremented from 1 to the last element of the second array, in increments of 1, equating a third variable to the product of the element of the first array corresponding to the index, and the element of the initial array corresponding to the element of the third array corresponding to the index;    if the index is less than or equal to the element of the second array corresponding to the first variable, equating the second variable to the sum of the second variable and the third variable;    if the index is greater than the element of the second array corresponding to the first variable, equating the element of the resulting array corresponding to the first variable to the second variable, incrementing the first variable by 1, and equating the second variable to a particular value.    
     
     
         74 . The method of  claim 73  wherein the set of instructions is predicated.  
     
     
         75 . The method of  claim 73  further comprising the step of prefetching the elements of the first array and the elements of the third array from memory.  
     
     
         76 . The method of  claim 73  further comprising an allocation control mechanism wherein the allocation control mechanism separates the elements with temporal locality from the elements with spatial locality.  
     
     
         77 . The method of  claim 73  further comprising the step of storing the elements with temporal locality in a cache memory.  
     
     
         78 . The method of  claim 73  further comprising the step of striding through the elements with spatial locality.  
     
     
         79 . The method of  claim 73  wherein the elements of the first array and the elements of the third array maintain spatial locality.  
     
     
         80 . The method of  claim 73  wherein the elements of the initial array maintain temporal locality.  
     
     
         81 . The method of  claim 73  wherein p is greater than 1.  
     
     
         82 . A computer system, comprising a microprocessor and a medium containing instructions, wherein the instructions, when executed by a computer, cause the computer to multiply a matrix having m rows and n columns containing non-zero elements and zero elements by an initial array having n rows and p columns and produce a resulting array having m rows and p columns, by performing the steps of: 
 creating a first array of elements containing the non-zero elements of the matrix;    creating a second array of elements containing the row position of the last non-zero element in each row of the matrix;    creating a third array of elements containing the column position of each non-zero element of the matrix;    executing a set of instructions for each column of the initial array and the resulting array, incremented from 1 top in increments of 1, initializing a first variable;    initializing a second variable;    for an index incremented from 1 to the last element of the second array, in increments of 1, equating a third variable to the product of the element of the first array corresponding to the index, and the element of the initial array corresponding to the element of the third array corresponding to the index;    if the index is less than or equal to the element of the second array corresponding to the first variable, equating the second variable to the sum of the second variable and the third variable;    if the index is greater than the element of the second array corresponding to the first variable, equating the element of the resulting array corresponding to the first variable to the second variable, incrementing the first variable by 1, and equating the second variable to a particular value.    
     
     
         83 . The computer system of  claim 82  wherein the set of instructions is predicated.  
     
     
         84 . The computer system of  claim 82  further comprising the step of prefetching the elements of the first array and the elements of the third array from memory.  
     
     
         85 . The computer system of  claim 82  further comprising an allocation control mechanism wherein the allocation control mechanism separates the elements with temporal locality from the elements with spatial locality.  
     
     
         86 . The computer system of  claim 82  further comprising the step of storing the elements with temporal locality in a cache memory.  
     
     
         87 . The computer system of  claim 82  further comprising the step of striding through the elements with spatial locality.  
     
     
         88 . The computer system of  claim 82  where in the elements of the first array and the elements of the third array maintain spatial locality.  
     
     
         89 . The computer system of  claim 82  wherein the elements of the initial array maintain temporal locality.  
     
     
         90 . The computer system of  claim 82  wherein p is greater than 1.  
     
     
         91 . A computer readable medium for storing instructions which, when executed by a computer, cause the computer to multiply a matrix having rows and columns containing non-zero elements and zero elements by a vector and produce a resulting vector, by performing the steps of: 
 creating a first array of elements containing the non-zero elements of the matrix;    creating a second array of elements containing the row position of the last non-zero element in each row of the matrix;    creating a third array of elements containing the column position of each non-zero element of the matrix;    initializing a first variable;    initializing a second variable;    executing a set of instructions for an index incremented from 1 to the last element of the second array, in increments of 1, if the index is less than or equal to the element of the second array corresponding to the first variable, equating the second variable to the sum of the second variable and the product of the element of the first array corresponding to the index, and the element of the vector corresponding to the element of the third array corresponding to the index;    if the index is greater than the element of the second array corresponding to the first variable, equating the element of the resulting vector corresponding to the first variable to the second variable, incrementing the first variable by 1, and equating the second variable to a particular value.    
     
     
         92 . The computer readable medium of  claim 91  wherein the set of instructions is predicated.  
     
     
         93 . The computer readable medium of  claim 91  further comprising the step of prefetching the elements of the first array and the elements of the third array from memory.  
     
     
         94 . The computer readable medium of  claim 91  further comprising an allocation control mechanism wherein the allocation control mechanism separates the elements with temporal locality from the elements with spatial locality.  
     
     
         95 . The computer readable medium of  claim 91  further comprising the step of storing the elements with temporal locality in a cache memory.  
     
     
         96 . The computer readable medium of  claim 91  further comprising the step of striding through the elements with spatial locality.  
     
     
         97 . The computer readable medium of  claim 91  wherein the elements of the first array and the elements of the third array maintain spatial locality.  
     
     
         98 . The computer readable medium of  claim 91  wherein the elements of the vector maintain temporal locality.  
     
     
         99 . A method for causing a computer to multiply a matrix having rows and columns containing non-zero elements and zero elements by a vector and produce a resulting vector, comprising the steps of: 
 creating a first array of elements containing the non-zero elements of the matrix;    creating a second array of elements containing the row position of the last non-zero element in each row of the matrix;    creating a third array of elements containing the column position of each non-zero element of the matrix;    initializing a first variable;    initializing a second variable;    executing a set of instructions for an index incremented from 1 to the last element of the second array, in increments of 1, if the index is less than or equal to the element of the second array corresponding to the first variable, equating the second variable to the sum of the second variable and the product of the element of the first array corresponding to the index, and the element of the vector corresponding to the element of the third array corresponding to the index;    if the index is greater than the element of the second array corresponding to the first variable, equating the element of the resulting vector corresponding to the first variable to the second variable, incrementing the first variable by 1, and equating the second variable to a particular value.    
     
     
         100 . The method of  claim 99  wherein the set of instructions is predicated.  
     
     
         101 . The method of  claim 99  further comprising the step of prefetching the elements of the first array and the elements of the third array from memory.  
     
     
         102 . The method of  claim 99  further comprising an allocation control mechanism wherein the allocation control mechanism separates the elements with temporal locality from the elements with spatial locality.  
     
     
         103 . The method of  claim 99  further comprising the step of storing the elements with temporal locality in a cache memory.  
     
     
         104 . The method of  claim 99  further comprising the step of striding through the elements with spatial locality.  
     
     
         105 . The method of  claim 99  wherein the elements of the first array and the elements of the third array maintain spatial locality.  
     
     
         106 . The method of  claim 99  wherein the elements of the vector maintain temporal locality.  
     
     
         107 . A computer system, comprising a microprocessor and a medium containing instructions, wherein the instructions, when executed by a computer, cause the computer to multiply a matrix having rows and columns containing non-zero elements and zero elements by a vector and produce a resulting vector, by performing the steps of: 
 creating a first array of elements containing the non-zero elements of the matrix;    creating a second array of elements containing the row position of the last non-zero element in each row of the matrix;    creating a third array of elements containing the column position of each non-zero element of the matrix;    initializing a first variable;    initializing a second variable;    executing a set of instructions for an index incremented from 1 to the last element of the second array, in increments of 1, if the index is less than or equal to the element of the second array corresponding to the first variable, equating the second variable to the sum of the second variable and the product of the element of the first array corresponding to the index, and the element of the vector corresponding to the element of the third array corresponding to the index;    if the index is greater than the element of the second array corresponding to the first variable, equating the element of the resulting vector corresponding to the first variable to the second variable, incrementing the first variable by 1, and    equating the second variable to a particular value.    
     
     
         108 . The computer system of  claim 107  wherein the set of instructions is predicated.  
     
     
         109 . The computer system of  claim 107  further comprising the step of prefetching the elements of the first array and the elements of the third array from memory.  
     
     
         110 . The computer system of  claim 107  further comprising an allocation control mechanism wherein the allocation control mechanism separates the elements with temporal locality from the elements with spatial locality.  
     
     
         111 . The computer system of  claim 107  further comprising the step of storing the elements with temporal locality in a cache memory.  
     
     
         112 . The computer system of  claim 107  further comprising the step of striding through the elements with spatial locality.  
     
     
         113 . The computer system of  claim 107  wherein the elements of the first array and the elements of the third array maintain spatial locality.  
     
     
         114 . The computer system of  claim 107  wherein the elements of the vector maintain temporal locality.  
     
     
         115 . A computer readable medium for storing instructions which, when executed by a computer, cause the computer to multiply a matrix having rows and columns containing non-zero elements and zero elements by a vector and produce a resulting vector, by performing the steps of: 
 creating a first array of elements containing the non-zero elements of the matrix;    creating a second array of elements containing the row position of the last non-zero element in each row of the matrix;    creating a third array of elements containing the column position of each non-zero element of the matrix;    initializing a first variable;    initializing a second variable;    initializing a third variable;    executing a set of instructions for an index incremented from 1 to the last element of the second array, in increments of 2, if the index is less than or equal to the element of the second array corresponding to the first variable, equating the second variable to the sum of the third variable and the product of the element of the first array corresponding to the index, and the element of the vector corresponding to the element of the third array corresponding to the index;    if the index is greater than the element of the second array corresponding to the first variable, equating the element of the resulting vector corresponding to the first variable to the third variable, incrementing the first variable by 1, and equating the second variable to the product of the element of the first array corresponding to the index, and    the element of the vector corresponding to the element of the third array corresponding to the index;    if the index+1 is less than or equal to the element of the second array corresponding to the first variable, equating the third variable to the sum of the second variable and the product of the element of the first array corresponding to the index+1, and the element of the vector corresponding to the element of the third array corresponding to the index+1;    if the index+1 is greater than the element of the second array corresponding to the first variable, equating the element of the resulting vector corresponding to the first variable to the second variable, incrementing the first variable by 1, and equating the third variable to the product of the element of the first array corresponding to the index+1, and the element of the vector corresponding to the element of the third array corresponding to the index+1; and then equating the element of the resulting vector corresponding to the first variable to the third variable when the last element of the second array is even.    
     
     
         116 . The computer readable medium of  claim 15  wherein the set of instructions is predicated.  
     
     
         117 . The computer readable medium of  claim 115  further comprising the step of prefetching the elements of the first array and the elements of the third array from memory.  
     
     
         118 . The computer readable medium of  claim 115  further comprising an allocation control mechanism wherein the allocation control mechanism separates the elements with temporal locality from the elements with spatial locality.  
     
     
         119 . The computer readable medium of  claim 115  further comprising the step of storing the elements with temporal locality in a cache memory.  
     
     
         120 . The computer readable medium of  claim 115  further comprising the step of striding through the elements with spatial locality.  
     
     
         121 . The computer readable medium of  claim 115  wherein the elements of the first array and the elements of the third array maintain spatial locality.  
     
     
         122 . The computer readable medium of  claim 15  wherein the elements of the vector maintain temporal locality.  
     
     
         123 . A method for causing a computer to multiply a matrix having rows and columns containing non-zero elements and zero elements by a vector and produce a resulting vector, comprising the steps of: 
 creating a first array of elements containing the non-zero elements of the matrix;    creating a second array of elements containing the row position of the last non-zero element in each row of the matrix;    creating a third array of elements containing the column position of each non-zero element of the matrix;    initializing a first variable;    initializing a second variable;    initializing a third variable;    executing a set of instructions for an index incremented from 1 to the last element of the second array, in increments of 2, if the index is less than or equal to the element of the second array corresponding to the first variable, equating the second variable to the sum of the third variable and the product of the element of the first array corresponding to the index, and the element of the vector corresponding to the element of the third array corresponding to the index;    if the index is greater than the element of the second array corresponding to the first variable, equating the element of the resulting vector corresponding to the first variable to the third variable, incrementing the first variable by 1, and equating the second variable to the product of the element of the first array corresponding to the index, and the element of the vector corresponding to the element of the third array corresponding to the index;    if the index+1 is less than or equal to the element of the second array corresponding to the first variable, equating the third variable to the sum of the second variable and the product of the element of the first array corresponding to the index+1, and the element of the vector corresponding to the element of the third array corresponding to the index+1;    if the index+1 is greater than the element of the second array corresponding to the first variable, equating the element of the resulting vector corresponding to the first variable to the second variable, incrementing the first variable by 1, and equating the third variable to the product of the element of the first array corresponding to the index+1, and the element of the vector corresponding to the element of the third array corresponding to the index+1; and then equating the element of the resulting vector corresponding to the first variable to the third variable only if the last element of the second array is even.    
     
     
         124 . The method of  claim 123  wherein the set of instructions is predicated.  
     
     
         125 . The method of  claim 123  further comprising the step of prefetching the elements of the first array and the elements of the third array from memory.  
     
     
         126 . The method of  claim 123  further comprising an allocation control mechanism wherein the allocation control mechanism separates the elements with temporal locality from the elements with spatial locality.  
     
     
         127 . The method of  claim 123  further comprising the step of storing the elements with temporal locality in a cache memory.  
     
     
         128 . The method of  claim 123  further comprising the step of striding through the elements with spatial locality.  
     
     
         129 . The method of  claim 123  wherein the elements of the first array and the elements of the third array maintain spatial locality.  
     
     
         130 . The method of  claim 123  wherein the elements of the vector maintain temporal locality.  
     
     
         131 . A computer system, comprising a microprocessor and a medium containing instructions, wherein the instructions, when executed by a computer, cause the computer to multiply a matrix having rows and columns containing non-zero elements and zero elements by a vector and produce a resulting vector, by performing the steps of: 
 creating a first array of elements containing the non-zero elements of the matrix;    creating a second array of elements containing the row position of the last non-zero element in each row of the matrix;    creating a third array of elements containing the column position of each non-zero element of the matrix;    initializing a first variable;    initializing a second variable;    initializing a third variable;    executing a set of instructions for an index incremented from 1 to the last element of the second array, in increments of 2, if the index is less than or equal to the element of the second array corresponding to the first variable, equating the second variable to the sum of the third variable and the product of the element of the first array corresponding to the index, and the element of the vector corresponding to the element of the third array corresponding to the index;    if the index is greater than the element of the second array corresponding to the first variable, equating the element of the resulting vector corresponding to the first variable to the third variable, incrementing the first variable by 1, and equating the second variable to the product of the element of the first array corresponding to the index, and the element of the vector corresponding to the element of the third array corresponding to the index;    if the index+1 is less than or equal to the element of the second array corresponding to the first variable, equating the third variable to the sum of the second variable and the product of the element of the first array corresponding to the index+1, and the element of the vector corresponding to the element of the third array corresponding to the index+1;    if the index+1 is greater than the element of the second array corresponding to the first variable, equating the element of the resulting vector corresponding to the first variable to the second variable, incrementing the first variable by 1, and equating the third variable to the product of the element of the first array corresponding to the index+1, and the element of the vector corresponding to the element of the third array corresponding to the index+1; and    then equating the element of the resulting vector corresponding to the first variable to the third variable when the last element of the second array is even.    
     
     
         132 . The computer system of  claim 131  wherein the set of instructions is predicated.  
     
     
         133 . The computer system of  claim 131  further comprising the step of prefetching the elements of the first array and the elements of the third array from memory.  
     
     
         134 . The computer system of  claim 131  further comprising an allocation control mechanism wherein the allocation control mechanism separates the elements with temporal locality from the elements with spatial locality.  
     
     
         135 . The computer system of  claim 131  further comprising the step of storing the elements with temporal locality in a cache memory.  
     
     
         136 . The computer system of  claim 131  further comprising the step of striding through the elements with spatial locality.  
     
     
         137 . The computer system of  claim 131  wherein the elements of the first array and the elements of the third array maintain spatial locality.  
     
     
         138 . The computer system of  claim 131  wherein the elements of the vector maintain temporal locality.

Join the waitlist — get patent alerts

Track US2002161812A1 — get alerts on status changes and closely related new filings.

We store only your email — no account needed. See our privacy policy.