search

adda-team / adda

ADDA - light scattering simulator based on the discrete dipole approximation
GNU General Public License v3.0
95 stars 56 forks source link

Circulant-type preconditioners #244

Open myurkin opened 6 years ago

myurkin commented 6 years ago

Follows from #24. The keywords to start searching are "Strohner-type" and "Chan-type".

S.A. Goreinov mentioned at ELS 12 conference that they had very positive experience with such preconditioners for very similar problems - the ones described in

A. Shcherbakov et al. "Novel approach for modeling optical properties of systems containing large number of metal nanoparticles", in Electromagnetic and Light Scattering XII: Conference Proceedings, pp. 274-277 (2010). http://www.helsinki.fi/els/articles/69/

myurkin commented 4 years ago

Recently, this idea has been discussed in

  1. Groth S.P., Polimeridis A.G., Tambova A., and White J.K. Circulant preconditioning in the volume integral equation method for silicon photonics, J. Opt. Soc. Am. A 36, 1079–1088 (2019).
  2. Groth S.P., Polimeridis A.G., and White J.K. Accelerating the discrete dipole approximation via circulant preconditioning, J. Quant. Spectrosc. Radiat. Transfer 240, 106689 (2020).

And it is implemented in open-source VoxScatter - should be easy to perform additional tests if needed.

The conclusion is somewhat mixed. For very oblate or prolate particles, it definitely helps, since 1D and 2D circulant preconditioners are used (they do not require a lot of extra resources for such problems). But it is not clear, how this extends to 3D shapes with comparable dimensions along different axes. For them 1D and 2D preconditioners are too slow per each matrix-vector multiplication (scale worse with size, i.e. with larger power), while 3D ones incur a lot of approximations - hence, do not significantly reduce Niter.

myurkin commented 1 year ago

Another case, where circulant preconditioners lead to significant improvement is for a particle inside a multi-layered substrate, since then the FFT along the z-axis cannot be employed anyway. See: Chaumet P.C., Maire G., and Sentenac A. Accelerating the discrete dipole approximation by initializing with a scalar solution and using a circulant preconditioning, J. Quant. Spectrosc. Radiat. Transfer 298, 108505 (2023).