Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[RFC] Provide built-in matrix-free iterative solvers #7634

Closed
houkensjtu opened this issue Mar 22, 2023 · 2 comments
Closed

[RFC] Provide built-in matrix-free iterative solvers #7634

houkensjtu opened this issue Mar 22, 2023 · 2 comments
Assignees
Labels
feature request Suggest an idea on this project RFC

Comments

@houkensjtu
Copy link
Contributor

houkensjtu commented Mar 22, 2023

Proposed feature

The purpose of this RFC is to discuss the possibility of adding a set of basic matrix-free iterative solvers, including conjugate-gradient (CG), BiCG, and BiCGSTAB to ti.linalg. The solvers target at solving

$$ Ax = b $$

where $A$ is a $n \times n$ matrix and $n$ is the number of unknowns.

Current status

Currently, users have two options if they need to solve a set of large-scale linear equations.

  1. Use the SparseMatrix API to build a sparse matrix, and then solve it using ti.linalg.SparseSolver.
  2. Implement their own linear solvers in Taichi language.

Note 1: We limit the scope of this topic to "large-scale" problems. Inverse of relative small matrices can be solved using the inverse() method provided in the taichi.math module.

Note 2: The development of the SparseMatrix solvers is well-documented in Issue #2906

Solution 1 is reasonably easy to use except that it does require the user to explicitly build-up the SparseMatrix themselves before solving (see documentation here).

As for solution 2, while writing an iterative solver on one's own provide great flexibility to users and does keep the language itself simple, we found the needs for a set of basic iterative solvers are quite common in entry-level users.

Overview of the plan

We can implement a set of basic matrix-free iterative solvers in native Taichi language. To represent the coefficient matrix A, we can implement a LinearOperator class for a user to transform their compute kernels to a "matrix-like" object.

# Implementation code not visible to users
@ti.data_oriented
class LinearOperator:
    def __init__(self, matvec):
        self.matvec = matvec

    def _matvec(self, x):
        # Default matvec behavior here
        
    def matvec(self, x):
        # Extra shape check here
        self._matvec(x, Ax)

The class will be implemented in a separate module iterative_solver.py under python/taichi/linalg so that it can be distinguished from the current SparseMatrixSolver family.

Use case

The user can pass a Taichi kernel to LinearOperator to create their "matrix-free" matrix. Here, the input of the kernel will be a ti.field of arbitrary shape, as long as the dimension of v and mv matches:

# User code
@ti.kernel
def compute_Ax(v:ti.template(), mv:ti.template()):  # v : vector, mv: matrix-vector product
    for i, j in v:
        l = v[i - 1, j] if i - 1 >= 0 else 0.0
        r = v[i + 1, j] if i + 1 <= GRID - 1 else 0.0
        t = v[i, j + 1] if j + 1 <= GRID - 1 else 0.0
        b = v[i, j - 1] if j - 1 >= 0 else 0.0
        mv[i, j] = 4 * v[i, j] - l - r - t - b

A = LinearOperator(compute_Ax)

This way, there will be no explicit stored matrix (thus the name matrix-free) and the A can be used for matrix-vector multiplication (which is required in most iterative methods). Notice that in this case, there will be no shape checking because the matvec() method is overwritten by the user.

Alternatively, user can create subclass of the LinearOperator class if they wish to implement their own:

class MyLinearOperator(LinearOperator):
    def __init__(self):
        ...
    def _matvec(self, x):
        ...

Here, when a user call matvec() method, extra shape checking will happen as it's inherited from the LinearOperator parent class.
Finally, we will provide a set of iterative solvers as Python functions, with similar API design to Scipy:

# Implementation code not visible to users
def cg(A, b, x, tol=1e-6, maxiter=5000):
    ...

def bicg(A, b, x, tol=1e-6, maxiter=5000):
    ...

def bicgstab(A, b, x, tol=1e-6, maxiter=5000):
    ...

and the user can call our pre-coded solvers simply by:

cg(A, b, x)

Additional comments

In Scipy, the LinearOperator class encourages the user to create their own subclass of it instead of creating an instance of it directly. Shall we follow the same path here in Taichi? Please let me know!

@houkensjtu houkensjtu added feature request Suggest an idea on this project RFC labels Mar 22, 2023
@houkensjtu houkensjtu self-assigned this Mar 22, 2023
@github-project-automation github-project-automation bot moved this to Untriaged in Taichi Lang Mar 22, 2023
@neozhaoliang neozhaoliang moved this from Untriaged to Todo in Taichi Lang Mar 24, 2023
@neozhaoliang neozhaoliang moved this from Todo to In Progress in Taichi Lang Mar 24, 2023
houkensjtu added a commit that referenced this issue Apr 7, 2023
…-lang (#7690)

Issue: #7634 

### Brief Summary
This PR implements a matrix-free CG (Conjugate-Gradient) solver in
Taichi. The solver targets to solve the linear equation system:

$$ Ax = b$$

where $A$ is implicitly represented as a `LinearOperator` instead of a
explicitly stored matrix, hence the name "matrix-free".

---------

Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
ailzhang pushed a commit to ailzhang/taichi that referenced this issue Apr 12, 2023
…-lang (taichi-dev#7690)

Issue: taichi-dev#7634 

### Brief Summary
This PR implements a matrix-free CG (Conjugate-Gradient) solver in
Taichi. The solver targets to solve the linear equation system:

$$ Ax = b$$

where $A$ is implicitly represented as a `LinearOperator` instead of a
explicitly stored matrix, hence the name "matrix-free".

---------

Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
@houkensjtu
Copy link
Contributor Author

The experimental matrix-free CG solver is now available under ti.linalg per PR#7690. This thread will be closed for now.

@github-project-automation github-project-automation bot moved this from In Progress to Done in Taichi Lang Apr 18, 2023
quadpixels pushed a commit to quadpixels/taichi that referenced this issue May 13, 2023
…-lang (taichi-dev#7690)

Issue: taichi-dev#7634 

### Brief Summary
This PR implements a matrix-free CG (Conjugate-Gradient) solver in
Taichi. The solver targets to solve the linear equation system:

$$ Ax = b$$

where $A$ is implicitly represented as a `LinearOperator` instead of a
explicitly stored matrix, hence the name "matrix-free".

---------

Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
@liuyunpu
Copy link

I have a question. If the Taichi kernel function "compute_Ax" need more input to compute Ax, for example i need variables from a class, so my compute_Ax should look like this:

@ti.kernel
def compute_Ax(self, v:ti.template(), mv:ti.template()):
    #compute Ax

how can i pass a kernel like this to LinearOperator? (writting all things needed to compute Ax in one kernel seems impossible in most physical simulations)
Another question, will there be a bicgstab solver for sparse matrix in cuda backend? the current cg solver in cuda can only solve positive-definite matrix. And more iterative solver would be nice.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
feature request Suggest an idea on this project RFC
Projects
Status: Done
Development

No branches or pull requests

2 participants