World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

THE IMPROVED PARALLEL ICGS METHOD FOR LARGE AND SPARSE UNSYMMETRIC LINEAR SYSTEMS

    For the solutions of large and sparse linear systems of equations with unsymmetric coefficient matrices, we propose an improved version of the Conjugate Gradient Squared method (ICGS) method. The algorithm is derived such that all inner products, matrix-vector multiplications and vector updates of a single iteration step are independent and communication time required for inner product can be overlapped efficiently with computation time of vector updates. Therefore, the cost of global communication on parallel distributed memory computers can be significantly reduced. The resulting ICGS algorithm maintains the favorable properties of the algorithm while not increasing computational costs. Data distribution suitable for both irregularly and regularly structured matrices based on the analysis of the non-zero matrix elements is also presented. Communication scheme is supported by overlapping execution of computation and communication to reduce waiting times. The efficiency of this method is demonstrated by numerical experimental results carried out on a parallel distributed memory system.

    References

    • A. Basermann, B. Reichel and C. Schelthoff, Parallel Computing 23(3), 381 (1997). Crossref, ISIGoogle Scholar
    • H. M.   Bücker and M.   Sauren , Parallel Numerical Computations with Applications , ed. L. T.   Yang ( Kluwer Academic Publishers , 1999 ) . Google Scholar
    • E.   de Sturler , A parallel variant of the GMRES(m) , Proceedings of the 13th IMACS World Congress on Computational and Applied Mathematics ( Criterion Press , 1991 ) . Google Scholar
    • E. de Sturler and H. A. van der Vorst. Reducing the effect of the global communication in GMRES(m) and CG on parallel distributed memory computers. Technical Report 832, Mathematical Institute, University of Utrecht, Utrecht, The Netherland, 1994 . Google Scholar
    • J. J.   Dongarra et al. , Solving Linear Systems on Vector and Shared Memory Computers ( SIAM , Philadelphia, PA , 1991 ) . Google Scholar
    • R. Fletcher, Numerical Analysis Dundee 1975, Lecture Notes in Mathematics 506, ed. G. A. Watson (Springer, Berlin, 1976) pp. 73–89. CrossrefGoogle Scholar
    • R. W. Freund, G. H. Golub and N. Nachtigal, Acta Numerica 57 (1991). Google Scholar
    • C. Lanczos. Solutions of systems of linear equations by minimized iterations. 49(1):33–53, 1952 . Google Scholar
    • M. Maheswaran, K. J. Webb and H. J. Siegel, International Journal of Supercomputing  (2000). Google Scholar
    • C. Pommerell. Solution of large unsymmetric systems of linear equations. PhD thesis, ETH, 1992 . Google Scholar
    • P. Sonneveld, SIAM Journal on Scientific and Statistical Computing 36 (1989). Google Scholar