SYSTEM AND METHOD FOR MULTI-COLOR DILU PRECONDITIONER

• US 20140046993A1
• Filed: 08/13/2012
• Published: 02/13/2014
• Est. Priority Date: 08/13/2012
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Castonguay, Patrice, Strzodka, Robert
• Granted Patent: US 9,798,698 B2
• Time in Patent Office: Days
• US Class Current: 708/446
• CPC Class Codes: G06F 17/12 Simultaneous equations , e.g. systems of linear equations

Abstract

A system and method for preconditioning or smoothing (e.g., multi-color DILU preconditioning) for iterative solving of a system of equations. The method includes accessing a matrix comprising a plurality of coefficients of a system of equations and accessing coloring information corresponding to the matrix. The method further includes determining a diagonal matrix based on the matrix and the coloring information corresponding to the matrix. The determining of the diagonal matrix may be determined in parallel on a per color basis. The method may further include determining an updated solution to the system of equations where the updated solution is determined in parallel on a per color basis using the diagonal matrix.

Claims

1. A method for preconditioning, said method comprising:

accessing a matrix comprising a plurality of coefficients of a system of linear equations;

accessing coloring information corresponding to said matrix; and

determining a diagonal matrix based on said matrix and said coloring information corresponding to said matrix, wherein said determining of said diagonal matrix is performed in parallel on a per color basis.

2. The method as described in claim 1 further comprising:

determining a preconditioning matrix based on said diagonal matrix.

3. The method as described in claim 2 wherein said preconditioning matrix is an incomplete lower and upper triangular decomposition with only diagonal modified (DILU) preconditioner.

4. The method as described in claim 1 further comprising:

accessing an initial solution.

5. The method as described in claim 4 further comprising:

determining an updated solution to said system of equations, wherein said updated solution is determined in parallel on a per color basis.

6. The method as described in claim 1 wherein said determining of said diagonal matrix is performed on a parallel hardware architecture.

7. The method as described in claim 6 wherein said parallel hardware architecture comprises a graphics processing unit (GPU).

8. A system for preconditioning, said system comprising:

a matrix access module operable to access a matrix corresponding to a system of equations;

a coloring access module operable to access color information corresponding to said matrix; and

a diagonal matrix determination module operable for determining a diagonal matrix based on said color information corresponding to said matrix in parallel on a per color basis, wherein said diagonal matrix is operable for computing an incomplete lower and upper triangular decomposition with only diagonal modified (DILU) preconditioner matrix.

9. The system as described in claim 8 wherein said diagonal matrix is determined by a graphical processing unit (GPU).

10. The system as described in claim 8 wherein said matrix corresponds to a plurality of coefficients of said system of equations.

11. The system as described in claim 8 further comprising:

a solution access module operable for accessing an initial solution to said system of equations.

12. The system as described in claim 11 further comprising:

an updated solution determination module operable for determining an updated solution based on said matrix, said initial solution, and said color information, wherein said determining of said updated solution is determined in parallel based on a per color basis.

13. The system as described in claim 12 wherein said updated solution module is operable to determine said updated solution based on a lower triangular solving phase and an upper triangular solving phase.

14. The system as described in claim 12 wherein said determining of said updated solution is determined by a GPU.

15. A method for solving a system of equations comprising:

accessing a matrix comprising coefficients of a system of equations;

accessing coloring information corresponding to said matrix;

determining a diagonal matrix based on said coloring information and said matrix, wherein said determining of said diagonal matrix is computed in parallel for each respective color of said coloring information; and

determining an updated solution to said system of equations, wherein said determining of said updated solution is based on an incomplete lower and upper triangular decomposition with only diagonal modified (DILU) preconditioner performed by a graphics processing unit (GPU) and said updated solution is computed in parallel on a per color basis.

16. The method as described in claim 15 wherein said determining of said diagonal matrix is determined by said GPU.

17. The method as described in claim 15 wherein said determining of said updated solution is based on an initial solution, said matrix, and said diagonal matrix.

18. The method as described in claim 15 wherein said updated solution is determined based on a lower triangular solving phase and an upper triangular solving phase.

19. The method as described in claim 15 wherein said updated solution is determined based on a common sparse matrix vector multiplication function.

20. The method as described in claim 15 wherein said determining of said updated solution is a portion of an algebraic multigrid iterative process.