This work presents a highly optimized computational framework for the Discrete Dipole Approximation, a numerical method for calculating the optical properties associated with a target of arbitrary geometry that is widely used in atmospheric, astrophysical and industrial simulations. Core optimizations include the bit-fielding of integer data and iterative methods that complement a new Discrete Fourier Transform (DFT) kernel, which efficiently calculates the matrix— vector products required by these iterative solution schemes. The new kernel performs the requisite 3-D DFTs as ensembles of 1-D transforms, and by doing so, is able to reduce the number of constituent 1-D transforms by 60% and the memory by over 80%. The optimizations also facilitate the use of parallel techniques to further enhance the performance. Complete OpenMP-based shared-memory and MPI-based distributed-memory implementations have been created to take full advantage of the various architectures. Several benchmarks of the new framework indicate extremely favorable performance and scalability.
Barrett, R., Berry, M., Chan, T.F., Demmel, J., Donato, J., Dongarra, J., Eijkhout, V., Pozo, R., Romine, C., and van der Vorst, H. (1994). Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd edition. Philadelphia, PA: SIAM .
2.
Bik, A.J.C. (2004). The Software Vectorization Handbook: Applying Multimedia Extensions for Maximum Performance. Hillsboro, OR, Intel Press.
3.
Bücker, H.M. and Sauren, M. (1996). A parallel version of the unsymmetric Lanczos algorithm and its application to QMR. Technical Report KFA-ZAM-IB-9606, Central Institute for Applied Mathematics, Research Centre Jülich , Germany.
4.
Davis, P.J. (1994). Circulant Matrices, 2nd edition. New York: Chelsea Publishing .
5.
DeVoe, H. (1964). Optical properties of molecular aggregates. I. Classical model of electronic absorption and refraction, J. Chem. Phys., 41: 393-400.
6.
DeVoe, H. (1965). Optical properties of molecular aggregates. II. Classical theory of the refraction, absorption and optical activity of solution and crystals, J. Chem. Phys., 43: 3199-3208.
7.
Draine, B.T. (1988). The Discrete-Dipole Approximation and its application to interstellar graphite grains, Astrophys. J., 333: 848-872.
8.
Draine, B.T. and Flatau, P.J. (1994). Discrete-Dipole Approximation for scattering calculations , J. Opt. Soc. Amer. A, 11: 1491-1499.
9.
Draine, B.T. and Flatau, P.J. (2004). User guide for the Discrete Dipole Approximation code DDSCAT 6.1. ArXiv Astrophysics e-prints. http://arxiv.org/abs/astro-ph/0409262v2.
10.
Draine, B.T. and Goodman, J. (1993). Beyond Clausius-Mossotti - wave propagation on a polarizable point lattice and the discrete dipole approximation, Astrophys. J., 405: 685-697.
11.
Fan, Z.H., Wang, D.X., Chen, R.S., and Yung, E.K.N. (2006). The application of iterative solvers in discrete dipole approximation method for computing electromagnetic scattering, Microwave Opt. Tech. Lett., 48: 1741-1746.
12.
Flatau, P.J. (1997). Improvements in the discrete-dipole approximation method of computing scattering and absorption, Opt. Lett. , 22(16): 1205-1207.
13.
Fletcher, R. (1975). Conjugate gradient methods for indefinite systems . In Proceedings of the Dundee Biennial Conference on Numerical Analysis, edited by G. A. Watson, Springer: Berlin, pp. 73-89.
14.
Freund, R. (1992). Conjugate gradient-type methods for linear systems with complex symmetric coefficient matrices, SIAM J. Sci. Comput., 13(1): 425-448.
15.
Freund, R. (1993). A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems, SIAM J. Sci. Comput., 14(2): 470-482.
16.
Freund, R. and Nachtigal, N. (1991). A quasi-minimal residual method for non-hermitian linear systems, Numer. Math., 60: 315-339.
17.
Freund, R. and Nachtigal, N. (1992). An implementation of the QMR method based on coupled two-term recurrences, SIAM J. Sci. Comput., 15(2): 313-337.
18.
Frigo, M. and Johnson, S.G. (1998). FFTW: An adaptive software architecture for the FFT, Proc. ICASSP, 3: 1381- 1384.
19.
Frigo, M. and Johnson, S.G. (2005). The design and implementation of FFTW3, Proceedings of the IEEE, (invited paper), Special Issue on Program Generation, Optimization, and Platform Adaptation, 93(2): 216-231.
20.
Golub, G.H. and Van Loan, C.F. (1996). Matrix Computations, 3rd edition. Baltimore, MD: The Johns Hopkins University Press.
21.
Goodman, J.J., Draine, B.T., and Flatau, P.J. (1991). Application of Fast Fourier Transform techniques to the Discrete Dipole Approximation, Opt. Lett., 16: 1198-1200.
22.
Hestenes, M.R. and Stiefel, E. (1952). Methods of conjugate gradient for solving linear systems, J. Res. Nat. Bur. Stand., 49: 409-436.
23.
Hoekstra, A.G. (1994). Computer Simulations of Elastic Light Scattering. Ph.D. thesis, University of Amsterdam, Holland.
24.
Hoekstra, A.G. and Sloot, P.M.A. (1995). Coupled dipole simulations of elastic light scattering on parallel systems, Int. J. Mod. Phys. C, 6: 663-679.
25.
Hoekstra, A.G., Grimminick, M., and Sloot, P.M.A. (1998). Large scale simulations of elastic light scattering by a fast discrete dipole approximation, Int. J. Mod. Phys. C, 9: 87- 102.
26.
Intel Corporation (2007). Intel Math Kernel Library (MKL), Version 9.1.
27.
Lumme, K. and Rahola, J. (1994). Light-scattering by porous dust particles in the discrete dipole approximation, Astrophys. J., 425(2): 653-667.
28.
Lumme, K. and Rahola, J. (1998). Comparison of light scattering by stochastically rough spheres, best-fit spheroids and spheres, J. Quant. Spectrosc. Radiat., 60(3): 439-450.
29.
Nebeker, B.M., Starr, G.W., and Hirleman, E. (1998). Evaluation of iteration methods used when modelling scattering features on surfaces using the discrete dipole approximation, J. Quant. Spectrosc. Radiat. Trans., 60: 493-500.
30.
Penttila, A., Zubko, E., Lumme, K., Muinonen, K., Yurkin, M.A., Draine, B.T., Rahola, J., Hoekstra, H.G., and Shkuratov, Y. (2007). Comparison between discrete dipole implementations and exact techniques, J. Quant. Spectrosc. Radiat. Trans. , 106(1-3): 417-436.
31.
Purcell, E.M. and Pennymaker, C.R. (1973). Scattering and absorption of light by non-spherical dielectric grains, Astrophys. J. , 186: 705-714.
32.
Rahola, J. (1996). Efficient solution of dense systems of linear equations in electromagnetic scattering calculations. Ph. D. thesis, Helsinki University of Technology, Finland.
33.
Rahola J. (1998). Applied Parallel Computing Large Scale Scientific and Industrial Problems: Iterative Solution of Dense Linear Systems Arising from Integral Equations, Vol. 1541 of Lecture Notes in Computer Science. Berlin/ Heidelberg: Springer .
34.
Shewchuk, J.R. (1994). An introduction to the conjugate gradient method without the agonizing pain. Technical Report CMU-CS-94-125. Pittsburgh, PA: School of Computer Science, Carnegie Mellon University.
35.
Sleijpen, G.L.G. and Fokkema, D.R. (1993). BiCGSTAB(L) for linear equations involving unsymmetric matrices with complex spectrum, Elect. Trans. Numer. Anal. , 1: 11-32.
36.
Sonneveld, P. (1989). CGS, a fast Lanczos-type solver for non-symmetric linear systems, SIAM J. Sci. Comput., 10(1): 36-52.
37.
van der Vorst, H.A. (1992). Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Comput., 13(2): 631- 644.
38.
Van Loan, C.F. (1992). Computational Frameworks for the Fast Fourier Transform. Philadelphia, PA: SIAM .
39.
Warren, S.G. (1984). Optical constants of ice from the ultraviolet to the microwave, Appl. Opt., 23(8): 218-229.
40.
Yeung, M. and Chan, T.F. (1999). ML(k)BiCGSTAB: A BiCGSTAB variant based on multiple Lanczos starting vectors, SIAM J. Sci. Comput., 21(4): 1263-1290.
41.
Yurkin, M.A. and Hoekstra, A.G. (2007). The discrete dipole approximation: An overview and recent developments, J. Quant. Spectrosc. Radiat. Trans. , 106: 558-589.
42.
Yurkin, M.A. and Hoekstra, A.G. (2008). User Manual for the Discrete Dipole Approximation Code "Amsterdam DDA", Version 0.78.2. http://www.science.uva.nl/research/scs/software/adda
43.
Yurkin, M.A., Maltsev, V.P., and Hoekstra, A.G. (2007). The discrete dipole approximation for simulation of light scattering by particles much larger than the wavelength, J. Quant. Spectrosc. Radiat. Trans., 106(1-3): 546-557.
44.
Zubko, E., Shkuratov, Y., Hart, M., Eversole, J., and Videen, G. (2003). Backscattering and negative polarization of agglomerate particles, Opt. Lett., 28: 1504-1506.
