Source-linked AI summary
Accelerating a FFT-based solver for numerical homogenization of periodic media by conjugate gradients
J. Zeman, J. Vondřejc, J. Novák, I. Marek
TL;DR
The original FFT-based homogenization solver converges poorly for composites with large coefficient jumps, while existing accelerations increase per-iteration cost. This note uses trigonometric collocation to obtain an FFT-efficient linear system solved by conjugate-gradient methods, and numerical experiments report faster convergence with comparable iteration cost.
Problem
The original FFT-based method has poor convergence for composites with large jumps in material coefficients, while existing accelerations increase computational cost per iteration.
Method
Trigonometric collocation produces a structured dense linear system with FFT-efficient matrix-vector products, which is solved using conjugate-gradient and biconjugate-gradient methods.
Results
The convergence rate is reported as proportional to the square root of phase contrast, while one iteration remains comparable in cost to the basic scheme.
Takeaways & Limitations
The accelerated method is reported to be insensitive to the choice of auxiliary reference medium while retaining comparable per-iteration cost.
Takeaways & Limitations
The methods fail to converge in the infinite contrast limit.
Abstract
from arXiv · showhide
In this short note, we present a new technique to accelerate the convergence of a FFT-based solver for numerical homogenization of complex periodic media proposed by Moulinec and Suquet in 1994. The approach proceeds from discretization of the governing integral equation by the trigonometric collocation method due to Vainikko (2000), to give a linear system which can be efficiently solved by conjugate gradient methods. Computational experiments confirm robustness of the algorithm with respect to its internal parameters and demonstrate significant increase of the convergence rate for problems with high-contrast coefficients at a low overhead per iteration.
1. Introduction
FFT-based homogenization handles general microstructures but converges poorly for composites with large coefficient jumps. The proposed trigonometric-collocation formulation enables Krylov-based solution of an efficiently FFT-evaluable linear system.
- FFT-based homogenization is suited to general microstructures represented as digital images.The method provides an alternative to approaches specialized for smooth inclusions.
- Large jumps in material coefficients cause poor convergence of the original FFT-based method.Existing accelerated schemes improve iteration counts but increase computational cost per iteration.
- The proposed approach discretizes the original FFT-based scheme using trigonometric collocation, producing a structured dense linear system.Its matrix-vector product can be computed efficiently using FFT.
- The resulting system is solved with Krylov subspace methods, including conjugate- and biconjugate-gradient methods.The paper compares these methods with the original scheme in two-dimensional scalar electrostatics.
2. Methodology
The method formulates periodic electrical conduction through a Lippmann–Schwinger equation, discretizes it by trigonometric collocation, and solves the resulting FFT-compatible linear system with Krylov methods, especially CG and BiCG.
- Problem setting: The periodic unit-cell problem models a Y-periodic electric field, divergence-free current, and constitutive relation j(x) = L(x) · e(x).
- Integral formulation: Introducing a constant reference conductivity L0 decomposes the current into reference-medium and contrast contributions, yielding a periodic Lippmann–Schwinger equation.
- Trigonometric collocation: Trigonometric collocation discretizes the unit cell on a regular periodic grid and approximates the searched field with a trigonometric polynomial.
- Linear system: The collocation equations form a system (I + B)e = e0 with a structured dense, generally non-symmetric matrix and grid-based field representations.
- Fast solution: Multiplication by B or B^T costs O(|N| log |N|) through forward and inverse FFTs, making the system suitable for iterative solvers.
- Iterative solution: The proposed approach applies Krylov subspace methods, specifically classical CG and BiCG, instead of the original Neumann-series solution strategy.
3. Results
The CG-based solver improves iteration and CPU-time performance over FFTH across conductivity contrasts, while its iteration count scales more favorably with phase contrast. Its residual-based termination is efficient, but convergence fails at infinite contrast.
- The model problem uses a 50% volume-fraction square array of circular particles, with N = (255, 255) discretization nodes and conductivities L = I and L = ρI.
- The reference-medium conductivity is parameterized by ω, with ω = 0.5 corresponding to optimal FFTH convergence.
- Residual- and equilibrium-based norms are roughly proportional at convergence, so the residual criterion is used subsequently because it requires fewer operations per iteration.
- CG reduces total CPU time across the full contrast range because its iteration overhead is about 10%, whereas BiCG costs about twice as much per iteration.
- CG iteration counts grow as √ρ rather than linearly with ρ for FFTH, although the CG-based method fails to converge at infinite contrast.
4. Conclusions
The note presents a conjugate-gradient acceleration of the FFT-based homogenization solver and reports faster convergence with comparable per-iteration cost. It also identifies failure at infinite contrast and outlines directions for further development.
- The non-symmetric system from trigonometric collocation can be solved using the standard conjugate gradient algorithm.
- The convergence rate is proportional to the square root of the phase contrast.
- The method fails to converge in the infinite contrast limit.
- The cost of one iteration remains comparable to the basic scheme and is insensitive to the choice of auxiliary reference medium.
- The computational experiments are a first step toward rigorous convergence analysis, multigrid acceleration, preconditioning, and extension to nonlinear problems.