What's Hot? Study Points to Iterative Methods for Nonsymmetric Linear Systems

March 9, 2001

Henk van der Vorst, shown here accepting the 1997 SIAG/LA Prize, learned recently that his work had been singled out for another distinction: In a study conducted by the Institute for Scientific Information, his 1992 paper on Bi-CGSTAB (SIAM Journal on Scientific and Statistical Computing) was found to be the most frequently cited mathematics paper published in the 90s.

Howard Elman

It is generally known that fast algorithms for solving large algebraic systems of equations are important for the development of efficient solvers in mathematical modeling. Just how important this problem has become was brought to light last fall when a SIAM paper on the topic was identified as the most heavily cited mathematics journal paper published in the 1990s. The paper in question is "Bi-CGSTAB-A Fast and Smoothly Converging Variant of BI-CG for the Solution of Nonsymmetric Linear Systems," by Henk van der Vorst, which appeared in SIAM Journal on Scientific and Statistical Computing in 1992. In a study performed in August 2000 by the Institute for Scientific Information (ISI), the paper was found to have been cited 379 times. As of this writing, there have been more than a hundred additional citations.

The general problem addressed in this work is the solution of nonsymmetric linear systems of equations by iterative methods. Iterative algorithms are needed when direct methods, based on Gaussian elimination, are too expensive. This is typically the case when high resolution is needed, especially for three-dimensional mathematical models, and the fill-in associated with sparse Gaussian elimination leads to prohibitively high storage and computational requirements.

Iterative algorithms avoid some of the costs associated with fill-in in matrix factors. If these techniques are to be useful, however, they must be reliable and rapidly convergent. The state of the art is much more advanced for symmetric positive-definite problems, where the conjugate gradient and multigrid algorithms are the methods of choice. Van der Vorst's work shows that the Bi-CGSTAB method exhibits smooth, stable convergence behavior in the nonsymmetric case.

A glance at the list of papers that reference the van der Vorst work, available from Science Citation Index, reveals that interest in these ideas comes from all branches of scientific computing. A random sample of applications, along with journals in which the papers are published, includes combustion (cited in Aerospace Science Technology), fluid dynamics (International Journal of Offshore and Polar Engineering), quantum chromodynamics (Physical Review D), numerical reservoir simulation (Society of Petroleum Engineering Journal), and electromagnetic scattering (IEEE Transactions on Magnetics).

Not surprisingly, the problem of fast iterative solvers for nonsymmetric systems has been heavily studied during the past twenty years, and van der Vorst's paper is one of many that address it. Indeed, the groundbreaking 1986 paper by Yousef Saad and Martin Schultz that introduced the GMRES algorithm (SISSC, Vol. 7, pages 856-869) has been cited more than 1100 times since its publication. Other heavily referenced papers include Peter Sonneveld's derivation of the "conjugate gradient squared" method (SISSC, Vol. 10, 1989, pages 36-52), with 338 citations, and Roland Freund and NoŽl Nachtigal's paper on the QMR method (Numerische Mathematk, Vol. 60, 1991, pages 315-339), with 215 citations. The second and third most frequently cited mathematics papers published in the 1990s come from the statistical literature. By way of contrast, Andrew Wiles's celebrated paper on Fermat's last theorem (Annals of Mathematics, 1995, pages 443-551), has fewer than a hundred scientific citations.

The Bi-CGSTAB statistic was discovered by ISI, publishers of Science Citation Index and the Web of Science Internet site, during the preparation of a study on the impact of science publications. It was also picked up by the Dutch newspaper de Volkstrant for an article in its science series; for interested readers who are fluent in Dutch, the news story appeared in de Volkstrant on September 30, 2000. The ISI study, titled Essential Science Indicators, is scheduled to be published this March.

Howard Elman is a professor of computer science at the University of Maryland. A member of the editorial board of SIAM Journal on Scientific Computing beginning in 1990, he was the associate editor who handled the Bi-CGSTAB paper; in January 1999, he became the journal's editor-in-chief.

Donate · Contact Us · Site Map · Join SIAM · My Account
Facebook Twitter Youtube linkedin google+