PIER B
 
Progress In Electromagnetics Research B
ISSN: 1937-6472
Home | Search | Notification | Authors | Submission | PIERS Home | EM Academy
Home > Vol. 68 > pp. 159-171

A COMPLEX MIX-SHIFTED PARALLEL QR ALGORITHM FOR THE C-METHOD

By C. Pan, R. Dusseaux, and N. Emad

Full Article PDF (279 KB)

Abstract:
The C-method is an exact method for analyzing gratings and rough surfaces. This method leads to large-size dense complex non-Hermitian eigenvalue. In this paper, we introduce a parallel QR algorithm that is specifically designed for the C-method. We define the ``early shift'' for the matrix according to the observed properties. We propose a combination of the ``early shift'', Wilkinson's shift and exceptional shift together to accelerate convergence. First, we use the ``early shift'' in order to have quick deflation of some eigenvalues. The multi-window bulge chain chasing and parallel aggressive early deflation are used. This approach ensures that most computations are performed in level 3 BLAS operations. The aggressive early deflation approach can detect deflation much quicker and accelerate convergence. Mixed MPI-OpenMP techniques are used for performing the codes to hybrid shared and distributed memory platforms. We validate our approach by comparison with experimental data for scattering patterns of two-dimensional rough surfaces.

Citation:
C. Pan, R. Dusseaux, and N. Emad, "A Complex Mix-Shifted Parallel QR Algorithm for the C-Method," Progress In Electromagnetics Research B, Vol. 68, 159-171, 2016.
doi:10.2528/PIERB16040806

References:
1. Chandezon, J., D. Maystre, and G. Raoult, "A new theoretical method for diffraction gratings and its numerical application," J. Optics (Paris), Vol. 11, 235-241, 1980.
doi:10.1088/0150-536X/11/4/005

2. Li, L. and J. Chandezon, "Improvement of the coordinate transformation method for surface-relief gratings with sharp edges," J. Opt. Soc. Am. A, 2247-2255, 1996.
doi:10.1364/JOSAA.13.002247

3. Granet, G., "Analysis of diffraction by surface-relief crossed gratings with use of the Chandezon method: Application to multilayer crossed gratings," J. Opt. Soc. Am. A, Vol. 15, 1121-1131, 1998.
doi:10.1364/JOSAA.15.001121

4. Ait Braham, K., R. Dusseaux, and G. Granet, "Scattering of electromagnetic waves from two-dimensional perfectly conducting random rough surfaces --- Study with the curvilinear coordinate method," Waves Random Complex Media, Vol. 18, 255-274, 2008.
doi:10.1080/17455030701749328

5. Dusseaux, R., K. Ait Braham, and G. Granet, "Implementation and validation of the curvilinear coordinate method for the scattering of electromagnetic waves from two-dimensional dielectric random rough surfaces," Waves Random Complex Media, Vol. 18, 551-570, 2008.
doi:10.1080/17455030802126913

6. Dusseaux, R., E. Vannier, O. Taconet, and G. Granet, "Study of backscatter signature for seedbed surface evolution under rainfall --- Influence of radar precision," Progress In Electromagnetics Research, Vol. 125, 415-437, 2012.
doi:10.2528/PIER11102807

7. Elfouhaily, T. M. and C. A. Guerin, "A critical survey of approximate scattering wave theories from random rough surfaces," Waves in Random and Complex Media, Vol. 14, R1-10, 2004.
doi:10.1088/0959-7174/14/4/R01

8. Bai, Z., J. W. Demmel, J. J. Dongarra, A. Ruhe, and H. van Der Vorst, Templates for the Solution of Algebraic Eigenvalue Problems. Software, Environments, and Tools, SIAM, 2000.

9. Golub, G. H. and F. Uhlig, "The QR algorithm: 50 years later its genesis by John Francis and Vera Kublanovskaya and subsequent developments," IMA J. Numer. Anal., Vol. 29, 467-485, 2009.
doi:10.1093/imanum/drp012

10. Golub, G. H. and C. F. Van Loan, Matrix Computations, Johns Hopkins University Press, Baltimore, 1996.

11. Braman, K., R. Byers, and R. Mathias, "The multi-shift QR algorithm. Part I: Maintaining well-focused shifts and level 3 performance," SIAM J. Matrix Anal. Appl., Vol. 23, 929-947, 2002.
doi:10.1137/S0895479801384573

12. Granat, R., B. Kagstrom, and D. Kressner, "A novel parallel QR algorithm for hybrid distributed memory HPC systems," SIAM J. Sci. Comput., Vol. 32, 2345-2378, 2010.
doi:10.1137/090756934

13. Braman, K., R. Byers, and R. Mathias, "The multi-shift QR algorithm. Part II: Aggressive early deflation," SIAM J. Matrix Anal. Appl., Vol. 23, 948-972, 2002.
doi:10.1137/S0895479801384585

14. MPI --- Messaging passing interface, See http://www.mcs.anl.gov/research/projects/mpi/.

15. OpenMP --- Open multi-processing, See http://openmp.org/wp/.

16. BLAS --- Basic linear algebra subprograms, See http://www.netlib.org/blas/.

17. ScaLAPACK --- Scalable linear algebra package, See http://www.netlib.org/scalapack/.

18. Kong, J. A., K. H. Ding, and C. O. Ao, Scattering of Electromagnetic Waves --- Numerical Simulations, Wiley-Interscience, New York, 2001.
doi:10.1002/0471224308

19. Afifi, S. and R. Dusseaux, "Scattering by anisotropic rough layered 2D interfaces," IEEE Trans. Antennas Propag., Vol. 60, 5315-5328, 2012.
doi:10.1109/TAP.2012.2207671

20. Berginc, G., "Small-slope approximation method: A further study of vector wave scattering from two-dimensional surfaces and comparison with experimental data," Progress In Electromagnetics Research, Vol. 37, 251-287, 2002.
doi:10.2528/PIER02070603

21. Johnson, J. T., L. Tsang, R. T. Shin, K. Pak, C. H. Chan, A. Ishimaru, and Y. Kuga, "Backscattering enhancement of electromagnetic waves from two-dimensional perfectly conducting random rough surfaces: A comparison of Monte-Carlo simulations with experimental data," IEEE Trans. Antennas Propag., Vol. 44, 748-756, 1996.
doi:10.1109/8.496261


© Copyright 2010 EMW Publishing. All Rights Reserved