Efficient matrix property determination with pipelining and parallelism
AssigneeCyber Atomics, Inc.
InventorRoy Batruni
Life of this patent
Estimating the term…
Abstract
Matrix processing includes: initializing a current matrix based at least in part on an original matrix; iteratively determining a matrix property using a plurality of iteration cycles, including, in an iteration cycle: partitioning the current matrix to obtain a plurality of partitions, wherein the plurality of partitions includes a submatrix; modifying the submatrix based at least in part on other partitions of the plurality of partitions to provide a current matrix for a next iteration; and continuing to iterate until a condition is met. Matrix processing further includes obtaining the matrix property from an iteration result; and outputting the matrix property.
Claims22
(canceled)
A system for matrix processing, comprising:
- one or more processors configured to:
- initialize a current matrix based at least in part on an original matrix;
- iteratively determine a matrix property using a plurality of iteration cycles, wherein:
- at least some of the iteratively determining the matrix property is performed on a plurality of processors in parallel;
- and
- an iteration cycle of the plurality of iteration cycles includes to:
- partition the current matrix to obtain a plurality of partitions, wherein the plurality of partitions includes a submatrix;
- modify the submatrix based at least in part on other partitions of the plurality of partitions to provide a current matrix for a next iteration;
- and
- continue to iterate until a condition is met;
- obtain the matrix property from an iteration result;
- and
- output the matrix property;
- and
- one or more memories coupled to the one or more processors and configured to provide one or more processors with instructions.
A matrix processing method, comprising:
- initializing a current matrix based at least in part on an original matrix;
- iteratively determining a matrix property using a plurality of iteration cycles, including, in an iteration cycle:
- partitioning the current matrix to obtain a plurality of partitions, wherein the plurality of partitions includes a submatrix;
- modifying the submatrix based at least in part on other partitions of the plurality of partitions to provide a current matrix for a next iteration;
- and
- continuing to iterate until a condition is met;
- obtaining the matrix property from an iteration result;
- and
- outputting the matrix property;
- wherein
- the iteratively determining of the matrix property is performed on a plurality of processors in parallel.
A computer program product for matrix processing, the computer program product being embodied in a tangible computer readable storage medium and comprising computer instructions for:
- initializing a current matrix based at least in part on an original matrix;
- iteratively determining a matrix property using a plurality of iteration cycles, including, in an iteration cycle:
- partitioning the current matrix to obtain a plurality of partitions, wherein the plurality of partitions includes a submatrix;
- modifying the submatrix based at least in part on other partitions of the plurality of partitions to provide a current matrix for a next iteration;
- and
- continuing to iterate until a condition is met;
- obtaining the matrix property from an iteration result;
- and
- outputting the matrix property;
- wherein
- the iteratively determining of the matrix property is performed on a plurality of processors in parallel.
A system, comprising:
- one or more processors configured to:
- initialize a current matrix based at least in part on an original matrix;
- iteratively determine singular values of the original matrix, wherein:
- at least some of the iteratively determining the singular values of the original matrix is performed on a plurality of processors in parallel;
- and
- an iteration cycle includes to:
- determine a Cholesky factor of the current matrix and a transpose of the Cholesky factor;
- reset the current matrix to be a product of the transpose of the Cholesky factor and the Cholesky factor;
- and
- continue to iterate until non-diagonal elements of the current matrix are zero or substantially close to zero;
- and
- obtain singular values from diagonal elements of the current matrix;
- and
- output the singular values;
- and
- one or more memories coupled to the one or more processors and configured to provide the one or more processors with instructions.
A method, comprising:
- initializing a current matrix based at least in part on an original matrix;
- iteratively determine singular values of the original matrix, including, in an iteration cycle:
- determining a Cholesky factor of the current matrix and a transpose of the Cholesky factor;
- resetting the current matrix to be a product of the transpose of the Cholesky factor and the Cholesky factor;
- and
- continuing to iterate until non-diagonal elements of the current matrix are zero or substantially close to zero;
- and
- obtaining singular values from diagonal elements of the current matrix;
- and
- outputting the singular values;
- wherein:
- at least some of the iteratively determining the singular values of the original matrix is performed on a plurality of processors in parallel.
A computer program product for matrix processing, the computer program product being embodied in a tangible computer readable storage medium and comprising computer instructions for:
- initializing a current matrix based at least in part on an original matrix;
- iteratively determine singular values of the original matrix, including, in an iteration cycle:
- determining a Cholesky factor of the current matrix and a transpose of the Cholesky factor;
- resetting the current matrix to be a product of the transpose of the Cholesky factor and the Cholesky factor;
- and
- continuing to iterate until non-diagonal elements of the current matrix are zero or substantially close to zero;
- and
- obtaining singular values from diagonal elements of the current matrix;
- and
- outputting the singular values;
- wherein:
- at least some of the iteratively determining the singular values of the original matrix is performed on a plurality of processors in parallel.
Dependencies are inferred from the claim text.