Vol. 68

Front:[PDF file] Back:[PDF file]
Latest Volume
All Volumes
All Issues
2016-06-30

A Complex Mix-Shifted Parallel QR Algorithm for the C-Method

By Cihui Pan, Richard Dusseaux, and Nahid Emad
Progress In Electromagnetics Research B, Vol. 68, 159-171, 2016
doi:10.2528/PIERB16040806

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


Cihui Pan, Richard Dusseaux, and Nahid 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
http://www.jpier.org/PIERB/pier.php?paper=16040806

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