System and method for multi-color dilu preconditioner

• US 9,798,698 B2
• Filed: 08/13/2012
• Issued: 10/24/2017
• Est. Priority Date: 08/13/2012
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Castonguay, Patrice, Strzodka, Robert
• Primary Examiner(s): Malzahn, David H
• Application Number:
  US13/584,575
• Publication Number:
  US 20140046993A1
• Time in Patent Office: 1,898 Days
• Field of Search: None
• 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 non-transitory computer-readable storage medium embodying instructions that, when executed by a processing device, cause the processing device to perform 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 of a preconditioning matrix of said matrix based on said matrix and said coloring information corresponding to said matrix, wherein said determining comprises;

assigning a plurality of execution threads to a plurality of elements of a respective color in said diagonal matrix; and

computing said plurality of elements of said respective color by executing said plurality of execution threads in said processing device.

2. The non-transitory computer-readable storage medium as described in claim 1, wherein the method further comprises:

determining said preconditioning matrix based on said diagonal matrix.

3. The non-transitory computer-readable storage medium 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 non-transitory computer-readable storage medium as described in claim 1 wherein the method further comprises:

accessing an initial solution.

5. The non-transitory computer-readable storage medium as described in claim 4 wherein the method further comprises:

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

6. The non-transitory computer-readable storage medium as described in claim herein said processing device comprises a graphics processing unit (GPU).

7. A system for preconditioning, said system comprising:

a processor; and

memory coupled to said processor and comprising instructions that comprise;

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, wherein said determining comprises;

assigning a plurality of execution threads to a plurality of elements of a respective color in said diagonal matrix; and

computing said plurality of elements of said respective color by executing said plurality of execution threads in parallel in said processing device, wherein said diagonal matrix determination module is operable for computing an incomplete lower and upper triangular decomposition with only diagonal modified (DILU) preconditioner matrix.

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

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

10. The system as described in claim 7, wherein said instructions further comprise:

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

11. The system as described in claim 10, wherein said instructions further comprise:

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 said updated solution is determined in parallel based on a per color basis.

12. The system as described in claim 11 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.

13. The system as described in claim 11 wherein said determining said updated solution is determined by a GPU.

14. A non-transitory computer-readable storage medium embodying instructions that, when executed by a processing device, cause the processing device to perform a method for solving a system of equations, said method comprising:

accessing a matrix comprising coefficients of a system of equations;

accessing coloring information corresponding to said matrix, wherein each row of said matrix is assigned with a particular color;

determining a diagonal matrix of a preconditioning matrix of said matrix, wherein said determining said diagonal matrix comprises;

assigning a plurality of execution threads to a plurality of elements of a respective color in said diagonal matrix; and

computing said plurality of elements of said respective color by executing said plurality of execution threads in parallel in said processing device; and

determining an updated solution to said system of equations, wherein said determining 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.

15. The non-transitory computer-readable storage medium as described in claim 14 wherein said determining of said diagonal matrix is determined by said GPU.

16. The non-transitory computer-readable storage medium as described in claim 14 wherein said determining said updated solution is based on an initial solution, said matrix, and said diagonal matrix.

17. The non-transitory computer-readable storage medium as described in claim 14 wherein said updated solution is determined based on a lower triangular solving phase and an upper triangular solving phase.

18. The non-transitory computer-readable storage medium as described in claim 14 wherein said updated solution is determined based on a common sparse matrix vector multiplication function.

19. The non-transitory computer-readable storage medium as described in claim 14 wherein said determining said updated solution is a portion of an algebraic multigrid iterative process.