Computer product and method for sparse matrices

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.