Norsk English

Numerical linear algebra

Efficient solution of large linear systems is essential to many scientific and industrial computations. We develop numerical methods and software that exploit the mathematical structure of the problem and the capabilities of modern hardware. Our expertise covers iterative solvers, preconditioning, multigrid and parallel computing on CPUs and GPUs.

Contact persons

When linear systems become the bottleneck

Large simulation models can give rise to systems of equations with millions of unknowns. Solving these systems often accounts for a substantial share of the computational time and memory requirements. The choice of algorithms and their implementation therefore determines how detailed a model can be and how many simulations can be performed.

We combine numerical linear algebra with a thorough understanding of the models behind the equations. This enables us to develop solvers that exploit mathematical structure, physical properties and available hardware.

We can help you:

  • Identify bottlenecks and improve the solution of large sparse linear systems.
  • Select, adapt and develop iterative solvers and preconditioners.
  • Exploit block structure and coupling between physical processes.
  • Develop multigrid, multiscale and domain decomposition methods.
  • Adapt algorithms and data structures for parallel execution on CPUs and GPUs.
  • Integrate and evaluate solution methods in existing software.

Contact our Applied Computational Science research group if linear solvers are limiting the performance or scale of your computations.

Preconditioning tailored to the problem

Iterative solvers approach the solution through successive computational steps. Their efficiency depends strongly on preconditioning, which uses an approximation of the system to make it easier to solve. A good preconditioner must be inexpensive to apply while capturing enough of the system's structure to reduce the number of iterations.

We work with Krylov subspace methods, incomplete factorisations, algebraic multigrid and block preconditioners. We adapt these methods to challenges such as strong material contrasts, anisotropy, irregular computational grids and differences in scale between variables.

In coupled problems, different parts of the linear system may have very different properties. We develop solution strategies that apply suitable methods to each subsystem while accounting for the coupling between them. Pressure-based CPR preconditioning in reservoir simulation is an important example of how physical insight can guide the design of efficient solvers.

Multigrid and multiscale methods

For an iterative method to converge quickly, information must propagate efficiently throughout the computational domain. Multigrid and multiscale methods combine local computations with corrections on coarser levels, addressing both local variations and long-range interactions.

We have extensive experience in developing and applying these methods to heterogeneous problems and complex computational grids. Our work includes constructing coarse problems, transferring information between levels and adapting the methods for parallel computing. Examples include the multiscale restriction-smoothed basis (MsRSB) method and its extension to preconditioning for flow and geomechanics.

Matching algorithms to hardware

The method with the fewest iterations is not necessarily the fastest. Preconditioner setup, memory traffic and communication between processors can account for a large share of the cost. On GPUs, sufficient parallelism and avoiding unnecessary data transfers are particularly important.

We develop algorithms and implementations together. This includes sparse matrix storage and operations, parallel preconditioners, reuse of computations, and the distribution of work across processors and accelerators. Our work on GPU-accelerated incomplete LU preconditioners illustrates this approach. The objective is to reduce total solution time and resource use for the problems the software needs to handle.

From numerical research to demanding industrial models

Our experience spans the development and testing of new algorithms through to their integration into large simulation tools. We have worked on linear solvers in open-source software as well as in-house and commercial simulators for industrial partners. 

Linear systems can change character during a simulation. We therefore evaluate methods over representative simulation runs, considering accuracy, robustness, memory use and total runtime. We also investigate how solver tolerances and the reuse of preconditioners affect the overall computation.

A collaboration can start with a specific matrix problem, a performance bottleneck in existing code or the need for a new solution strategy. We can contribute from analysis and method selection through to implementation and testing in your software.

Selected publications

Many of our methodological contributions have grown out of reservoir simulation, where large, coupled linear systems place stringent demands on robustness and computational efficiency. The papers below, however, address challenges that also arise in other areas of simulation: strong coefficient contrasts, coupling between physical processes and efficient parallelisation. These methods and the experience gained provide a foundation for developing solvers for other models with similar mathematical structures.