# US 2014/0196043 A1 · System and method for re-factorizing a square matrix into lower and upper triangular matrices on a parallel processor

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2014/0196043 A1
- Document ID: US20140196043A1
- Status: Published application
- Kind: A1
- Application number: 13/737,287
- Filed: 2013-01-09
- Published: 2014-07-10
- Earliest claimed: 2013-01-09
- Assignees: NVIDIA Corporation
- Applicants: Nvidia Corporation
- Inventors: Maxim Naumov; Sharanyan Chetlur; Lung Sheng Chien; Robert Strzodka; Philippe Vandermersch
- Web page: https://patentgrep.com/patent/US20140196043A1

## CPC

- G06F 9/46: Multiprogramming arrangements
- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- G06F 16/35: Clustering; Classification
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system and method for re-factorizing a square input matrix on a parallel processor. In one embodiment, the system includes: (1) a matrix generator operable to generate an intermediate matrix by embedding a permuted form of the input matrix in a zeroed-out sparsity pattern of a combination of lower and upper triangular matrices resulting from a prior LU factorization of a previous matrix having a same sparsity pattern, reordering to minimize fill-in and pivoting strategy as the input matrix and (2) a re-factorizer associated with the matrix generator and operable to use parallel threads to apply an incomplete-LU factorization with zero fill-in on the intermediate matrix.

## Claims

### Claim 1

A system for re-factorizing a square input matrix on a parallel processor, comprising:
a matrix generator operable to generate an intermediate matrix by embedding a permuted form of said input matrix in a zeroed-out sparsity pattern of a combination of lower and upper triangular matrices resulting from an LU factorization of a previous matrix having a same sparsity pattern, reordering to minimize fill-in and pivoting strategy as said input matrix; and
a re-factorizer associated with said matrix generator and operable to use parallel threads to apply an incomplete-LU factorization with zero fill-in on said intermediate matrix.

### Claim 2 (depends on 1)

The system as recited in claim 1 wherein said intermediate matrix generator is operable to embed said permuted form in said sparsity pattern.

### Claim 3 (depends on 1)

The system as recited in claim 1 wherein said re-factorizer is further operable to performing a symbolic analysis on said input matrix to group independent nodes representing columns thereof into levels representing data dependencies between said nodes.

### Claim 4 (depends on 1)

The system as recited in claim 1 wherein said re-factorizer is further operable to employ a merged compressed sparse row-compressed sparse column format in carrying out said incomplete-LU factorization with zero fill-in.

### Claim 5 (depends on 1)

The system as recited in claim 1 wherein said re-factorizer is further operable to compute grid and block launch parameters particular to each level in defining a configuration of said parallel threads.

### Claim 6 (depends on 1)

The system as recited in claim 1 wherein said re-factorizer is further operable to launch said parallel threads as two concurrent kernels per level of said subsequent matrix, one of said kernels operable to update multipliers in said level and another of said kernels operable to update remaining elements in said level.

### Claim 7 (depends on 6)

The system as recited in claim 6 wherein said re-factorizer is further operable with a SIMD processor to launch said parallel threads.

### Claim 8

A method of re-factorizing a square input matrix on a parallel processor, comprising:
generating an intermediate matrix by embedding a permuted form of said input matrix in a zeroed-out sparsity pattern of a combination of lower and upper triangular matrices resulting from an LU factorization of a previous matrix having a same sparsity pattern, reordering to minimize fill-in and pivoting strategy as said input matrix; and
using parallel threads to apply an incomplete-LU factorization with zero fill-in on said intermediate matrix.

### Claim 9 (depends on 8)

The method as recited in claim 8 wherein said embedding comprises embedding said permuted form in said sparsity pattern.

### Claim 10 (depends on 8)

The method as recited in claim 8 wherein said using comprises performing a symbolic analysis on said input matrix to group independent nodes representing columns thereof into levels representing data dependencies between said nodes.

### Claim 11 (depends on 8)

The method as recited in claim 8 wherein said using comprises employing a merged compressed sparse row-compressed sparse column format in carrying out said incomplete-LU factorization with zero fill-in.

### Claim 12 (depends on 8)

The method as recited in claim 8 wherein said using comprises computing grid and block launch parameters particular to each level in defining a configuration of said parallel threads.

### Claim 13 (depends on 8)

The method as recited in claim 8 wherein using comprises launching said parallel threads as two concurrent kernels per level of said subsequent matrix, one of said kernels operable to update multipliers in said level and another of said kernels operable to update remaining elements in said level.

### Claim 14 (depends on 13)

The method as recited in claim 13 wherein said using comprises employing a SIMD processor to launch said parallel threads.

### Claim 15

A SIMD processor, comprising:
lanes operable to process parallel threads;
a pipeline control unit system operable to control thread processing in said lanes; and
a system for employing said lanes and said pipeline control unit to re-factorize a square input matrix, including:
a matrix generator operable to generate an intermediate matrix by embedding a permuted form of said input matrix in a zeroed-out sparsity pattern of a combination of lower and upper triangular matrices resulting from an LU factorization of a previous matrix having a same sparsity pattern, reordering to minimize fill-in and pivoting strategy as said input matrix, and
a re-factorizer associated with said matrix generator and operable to transmit parallel threads to said pipeline control unit to apply an incomplete-LU factorization with zero fill-in on said intermediate matrix.

### Claim 16 (depends on 15)

The processor as recited in claim 15 wherein said intermediate matrix generator is operable to embed said permuted form in said sparsity pattern.

### Claim 17 (depends on 15)

The processor as recited in claim 15 wherein said re-factorizer is further operable to performing a symbolic analysis on said square matrix to group independent nodes representing columns thereof into levels representing data dependencies between said nodes.

### Claim 18 (depends on 15)

The processor as recited in claim 15 wherein said re-factorizer is further operable to employ a merged compressed sparse row-compressed sparse column format in carrying out said incomplete-LU factorization with zero fill-in.

### Claim 19 (depends on 15)

The processor as recited in claim 15 wherein said re-factorizer is further operable to compute grid and block launch parameters particular to each level in defining configuration of said parallel threads.

### Claim 20 (depends on 15)

The processor as recited in claim 15 wherein said re-factorizer is further operable to launch said parallel threads as two concurrent kernels per level of said intermediate matrix, one of said kernels operable to update multipliers in said level and another of said kernels operable to update remaining elements in said level.