Wim Vanroose

Siegfried Cools, Emrullah Fatih Yetkin, Emmanuel Agullo et al.

Pipelined Krylov subspace methods typically offer improved strong scaling on parallel HPC hardware compared to standard Krylov subspace methods for large and sparse linear systems. In pipelined methods the traditional synchronization bottleneck is mitigated by overlapping time-consuming global communications with useful computations. However, to achieve this communication hiding strategy, pipelined methods introduce additional recurrence relations for a number of auxiliary variables that are required to update the approximate solution. This paper aims at studying the influence of local rounding errors that are introduced by the additional recurrences in the pipelined Conjugate Gradient method. Specifically, we analyze the impact of local round-off effects on the attainable accuracy of the pipelined CG algorithm and compare to the traditional CG method. Furthermore, we estimate the gap between the true residual and the recursively computed residual used in the algorithm. Based on this estimate we suggest an automated residual replacement strategy to reduce the loss of attainable accuracy on the final iterative solution. The resulting pipelined CG method with residual replacement improves the maximal attainable accuracy of pipelined CG, while maintaining the efficient parallel performance of the pipelined method. This conclusion is substantiated by numerical results for a variety of benchmark problems.

Siegfried Cools, Bram Reps, Wim Vanroose

In this paper we construct and analyse a level-dependent coarsegrid correction scheme for indefinite Helmholtz problems. This adapted multigrid method is capable of solving the Helmholtz equation on the finest grid using a series of multigrid cycles with a grid-dependent complex shift, leading to a stable correction scheme on all levels. It is rigourously shown that the adaptation of the complex shift throughout the multigrid cycle maintains the functionality of the two-grid correction scheme, as no smooth modes are amplified in or added to the error. In addition, a sufficiently smoothing relaxation scheme should be applied to ensure damping of the oscillatory error components. Numerical experiments on various benchmark problems show the method to be competitive with or even outperform the current state-of-the-art multigrid-preconditioned Krylov methods, like e.g. CSL-preconditioned GMRES or BiCGStab.

Bram Reps, Wim Vanroose

This paper analyzes the Krylov convergence rate of a Helmholtz problem preconditioned with Multigrid. The multigrid method is applied to the Helmholtz problem formulated on a complex contour and uses GMRES as a smoother substitute at each level. A one-dimensional model is analyzed both in a continuous and discrete way. It is shown that the Krylov convergence rate of the continuous problem is independent of the wave number. The discrete problem, however, can deviate significantly from this bound due to a pitchfork in the spectrum. It is further shown in numerical experiments that the convergence rate of the Krylov method approaches the continuous bound as the grid distance $h$ gets small.

Siegfried Cools, Pieter Ghysels, Wim van Aarle et al.

Classical iterative methods for tomographic reconstruction include the class of Algebraic Reconstruction Techniques (ART). Convergence of these stationary linear iterative methods is however notably slow. In this paper we propose the use of Krylov solvers for tomographic linear inversion problems. These advanced iterative methods feature fast convergence at the expense of a higher computational cost per iteration, causing them to be generally uncompetitive without the inclusion of a suitable preconditioner. Combining elements from standard multigrid (MG) solvers and the theory of wavelets, a novel wavelet-based multi-level (WMG) preconditioner is introduced, which is shown to significantly speed-up Krylov convergence. The performance of the WMG-preconditioned Krylov method is analyzed through a spectral analysis, and the approach is compared to existing methods like the classical Simultaneous Iterative Reconstruction Technique (SIRT) and unpreconditioned Krylov methods on a 2D tomographic benchmark problem. Numerical experiments are promising, showing the method to be competitive with the classical Algebraic Reconstruction Techniques in terms of convergence speed and overall performance (CPU time) as well as precision of the reconstruction.

Bram Reps, Wim Vanroose, Hisham bin Zubair

Multigrid preconditioners and solvers for the indefinite Helmholtz equation suffer from non-stability of the stationary smoothers due to the indefinite spectrum of the operator. In this paper we explore GMRES as a replacement for the stationary smoothers of the standard multigrid method. This results in a robust and efficient solver for a complex shifted or stretched Helmholtz problem that can be used as a preconditioner. Very few GMRES iterations are required on each level to build a good multigrid method. The convergence behavior is compared to a theoretically derived stable polynomial smoother. We test this method on some benchmark problems and report on the observed convergence behavior.

Hisham bin Zubair, Bram Reps, Wim Vanroose

The Schrödinger equation defines the dynamics of quantum particles which has been an area of unabated interest in physics. We demonstrate how simple transformations of the Schrödinger equation leads to a coupled linear system, whereby each diagonal block is a high frequency Helmholtz problem. Based on this model, we derive indefinite Helmholtz model problems with strongly varying wavenumbers. We employ the iterative approach for their solution. In particular, we develop a preconditioner that has its spectrum restricted to a quadrant (of the complex plane) thereby making it easily invertible by multigrid methods with standard components. This multigrid preconditioner is used in conjuction with suitable Krylov-subspace methods for solving the indefinite Helmholtz model problems. The aim of this study is to report the feasbility of this preconditioner for the model problems. We compare this idea with the other prevalent preconditioning ideas, and discuss its merits. Results of numerical experiments are presented, which complement the proposed ideas, and show that this preconditioner may be used in an automatic setting.

Nico Schlömer, Wim Vanroose

This paper considers the extreme type-II Ginzburg--Landau equations, a nonlinear PDE model for describing the states of a wide range of superconductors. Based on properties of the Jacobian operator and an AMG strategy, a preconditioned Newton--Krylov method is constructed. After a finite-volume-type discretization, numerical experiments are done for representative two- and three-dimensional domains. Strong numerical evidence is provided that the number of Krylov iterations is independent of the dimension $n$ of the solution space, yielding an overall solver complexity of O(n).

Siegfried Cools, Wim Vanroose

This paper introduces and explores the class of expansion preconditioners EX(m) that forms a direct generalization to the classic complex shifted Laplace (CSL) preconditioner for Helmholtz problems. The construction of the EX(m) preconditioner is based upon a truncated Taylor series expansion of the original Helmholtz operator inverse. The expansion preconditioner is shown to significantly improve Krylov solver convergence rates for the Helmholtz problem for growing values of the number of series terms m. However, the addition of multiple terms in the expansion also increases the computational cost of applying the preconditioner. A thorough cost-benefit analysis of the addition of extra terms in the EX(m) preconditioner proves that the CSL or EX(1) preconditioner is the practically most efficient member of the expansion preconditioner class. Additionally, possible extensions to the expansion preconditioner class that further increase preconditioner efficiency are suggested.

Yuriy Bidasyuk, Wim Vanroose

The Schrödinger equation for two and tree-body problems is solved for scattering states in a hybrid representation where solutions are expanded in the eigenstates of the harmonic oscillator in the interaction region and on a finite difference grid in the near-- and far--field. The two representations are coupled through a high--order asymptotic formula that takes into account the function values and the third derivative in the classical turning points. For various examples the convergence is analyzed for various physics problems that use an expansion in a large number of oscillator states. The results show significant improvement over the JM-ECS method [Bidasyuk et al, Phys. Rev. C 82, 064603 (2010)].

Siegfried Cools, Jeffrey Cornelis, Wim Vanroose

Pipelined Krylov subspace methods (also referred to as communication-hiding methods) have been proposed in the literature as a scalable alternative to classic Krylov subspace algorithms for iteratively computing the solution to a large linear system in parallel. For symmetric and positive definite system matrices the pipelined Conjugate Gradient method outperforms its classic Conjugate Gradient counterpart on large scale distributed memory hardware by overlapping global communication with essential computations like the matrix-vector product, thus hiding global communication. A well-known drawback of the pipelining technique is the (possibly significant) loss of numerical stability. In this work a numerically stable variant of the pipelined Conjugate Gradient algorithm is presented that avoids the propagation of local rounding errors in the finite precision recurrence relations that construct the Krylov subspace basis. The multi-term recurrence relation for the basis vector is replaced by two-term recurrences, improving stability without increasing the overall computational cost of the algorithm. The proposed modification ensures that the pipelined Conjugate Gradient method is able to attain a highly accurate solution independently of the pipeline length. Numerical experiments demonstrate a combination of excellent parallel performance and improved maximal attainable accuracy for the new pipelined Conjugate Gradient algorithm. This work thus resolves one of the major practical restrictions for the useability of pipelined Krylov subspace methods.

Koen Ruymbeek, Wim Vanroose

Computed Tomography is a powerful imaging technique that allows non-destructive visualization of the interior of physical objects in different scientific areas. In traditional reconstruction techniques the object of interest is mostly considered to be static, which gives artefacts if the object is moving during the data acquisition. In this paper we present a method that, given only scan results of multiple successive scans, can estimate the motion and correct the CT-images for this motion assuming that the motion field is smooth over the complete domain using optical flow. The proposed method is validated on simulated scan data. The main contribution is that we show we can use the optical flow technique from imaging to correct CT-scan images for motion.

Siegfried Cools, Wim Vanroose

By reducing the number of global synchronization bottlenecks per iteration and hiding communication behind useful computational work, pipelined Krylov subspace methods achieve significantly improved parallel scalability on present-day HPC hardware. However, this typically comes at the cost of a reduced maximal attainable accuracy. This paper presents and compares several stabilized versions of the communication-hiding pipelined Conjugate Gradients method. The main novel contribution of this work is the reformulation of the multi-term recurrence pipelined CG algorithm by introducing shifts in the recursions for specific auxiliary variables. These shifts reduce the amplification of local rounding errors on the residual. The stability analysis presented in this work provides a rigorous method for selection of the optimal shift value in practice. It is shown that, given a proper choice for the shift parameter, the resulting shifted pipelined CG algorithm restores the attainable accuracy and displays nearly identical robustness to local rounding error propagation compared to classical CG. Numerical results on a variety of SPD benchmark problems compare different stabilization techniques for the pipelined CG algorithm, showing that the shifted pipelined CG algorithm is able to attain a high accuracy while displaying excellent parallel performance.

Nick Schenkels, Wim Vanroose

Many inverse problems can be described by a PDE model with unknown parameters that need to be calibrated based on measurements related to its solution. This can be seen as a constrained minimization problem where one wishes to minimize the mismatch between the observed data and the model predictions, including an extra regularization term, and use the PDE as a constraint. Often, a suitable regularization parameter is determined by solving the problem for a whole range of parameters -- e.g. using the L-curve -- which is computationally very expensive. In this paper we derive two methods that simultaneously solve the inverse problem and determine a suitable value for the regularization parameter. The first one is a direct generalization of the Generalized Arnoldi Tikhonov method for linear inverse problems. The second method is a novel method based on similar ideas, but with a number of advantages for nonlinear problems.

Nick Schenkels, Wim Vanroose

In this paper we derive a Newton type method to solve the non-linear system formed by combining the Tikhonov normal equations and Morozov's discrepancy principle. We prove that by placing a bound on the step size of the Newton iterations the method will always converge to the solution. By projecting the problem onto a low dimensional Krylov subspace and using the method to solve the projected non-linear system we show that we can reduce the computational cost of the method.

Nick Schenkels, Jan Sijbers, Wim van Aarle et al.

Phase contrast tomography is an alternative to classic absorption contrast tomography that leads to higher contrast reconstructions in many applications. We review how phase contrast data can be acquired by using a combination of phase and absorption gratings. Using algebraic reconstruction techniques the object can be reconstructed from the measured data. In order to solve the resulting linear system we propose the Generalized Bidiagonal Tikhonov (GBiT) method, an adaptation of the generalized Arnoldi-Tikhonov method that uses the bidiagonal decomposition of the matrix instead of the Arnoldi decomposition. We also study the effect of the finite difference operator in the model by examining the reconstructions with either a forward difference or a central difference approximation. We validate our conclusions with simulated and experimental data.

Bram Reps, Wim Vanroose, Hisham bin Zubair

This paper studies and analyzes a preconditioned Krylov solver for Helmholtz problems that are formulated with absorbing boundary layers based on complex coordinate stretching. The preconditioner problem is a Helmholtz problem where not only the coordinates in the absorbing layer have an imaginary part, but also the coordinates in the interior region. This results into a preconditioner problem that is invertible with a multigrid cycle. We give a numerical analysis based on the eigenvalues and evaluate the performance with several numerical experiments. The method is an alternative to the complex shifted Laplacian and it gives a comparable performance for the studied model problems.