7
$\begingroup$

I am Computer Scientist and now I am interested in matrix multiplication on GPUs. My research are focused on matrix free finite elements method where I multiply sparse matrix. Sparse matrix could multiply regular or matrix free. In general based on special coordinate function. I have a few general question: How popular is this method? Does any another name exist for this method? I am also looking for books and article concentrate on finite element method especially matrix free multiplication and I consider about general books and article. Because many article based on rather complicated examples like conjugate gradient method or something different. As I said in topic name I try to use this method in process tomography visualization.

$\endgroup$
6
$\begingroup$

Matrix-free method is a general name for a class of algorithms, rather than a particular method. For example, consider solving the linear equation $Ax=b.$ If you were to solve this this problem using the Gauss elimination method, for example, then you need to pre-compute all elements of $A$ and keep them during the algorithm. If you were to use Krylov-type iterative solvers, you need to multiply the matrix $A$ by a vector at every step. You can do it differently.

  1. Pre-compute $A$ and keep it in memory (as a sparse array, perhaps).
  2. Do not store $A,$ but re-compute (some of) its elements every time you need to multiply $A$ by a vector.

The first approach is not a matrix-free method, while the second approach is.

To answer your question now:

  • Matrix-free elements have been originally motivated by the lack of operative memory for computations. Although the problem is not solved in general yet, in many applications the remedy is found using the distributed-memory parallel computations or more efficient matrix formats, which allow to store matrix and avoid re-calculation of its elements.
  • Matrix-free method are indeed promising for GPUs, since it may be cheaper to re-compute elements of the matrix on the fast GPU core, than to deliver them to this core from the main memory.
$\endgroup$
7
$\begingroup$

To add to Dmitry's answer (copied over from the deleted version of this question):

Matrix-free finite elements are relatively well-known. For explicit methods for transient problems, this involves applying the finite element matrix using small reference matrices and geometry-specific transformations.

For implicit problems, this is usually done in conjunction with an iterative solver such as CG, GMRES, etc. Note that this typically also requires a preconditioner, many of which may not map well directly to GPUs. For nonlinear implicit problems, this may also be paired with a matrix-free approximation of the Jacobian in a linearization (see for example Ben Kirk's thesis for an application of matrix-free implicit methods in CFD).

For GPU-specific implementations of explicit methods, there is ample literature on matrix-free implementations of finite element (specifically Discontinuous Galerkin) methods; see, for example, Hesthaven/Warburton (not GPU specific, but implementation is similar) and Klockner et al.. For some literature on the GPU implementation of matrix-free implicit solvers, see Remacle, Gandham, Warburton, where they solve the heat equation using a two-grid overlapping additive Schwarz preconditioner.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.