Archive ScienceWatch

 ScienceWatch

FAST MOVING FRONTS

Alexander H.D. Cheng talks with ScienceWatch.com and answers a few questions about this month's Fast Moving Front in the field of Mathematics. The author has also sent along images of their work.
Cheng Article: Exponential convergence and H-c multiquadric collocation method for partial differential equations
Authors: Cheng, AHD;Golberg, MA;Kansa, EJ;Zammito, G
Journal: NUMER METHOD PARTIAL DIFFER E, 19 (5): 571-594 SEP 2003
Addresses: Univ Mississippi, Dept Civil Engn, 203 Carrier Hall,POB 1848, University, MS 38677 USA.
Univ Mississippi, Dept Civil Engn, University, MS 38677 USA.
Embry Riddle Aeronaut Univ, Oakland, CA 94621 USA.
(addresses have been truncated)

Why do you think your paper is highly cited?

I think it tackled an intriguing question: "Can we achieve higher and higher accuracy in numerical solutions of partial differential equations without refining the grid?" Refining the grid means significantly increasing the central processing unit (CPU) time. Without refining the grid means having a free lunch, which is against some fundamental principles in approximation theory, although certain mathematical proofs on the so-called multiquadric interpolation function seem to imply it. Is it our misunderstanding? Or is it indeed even possible? This paper sets out to prove or disprove it, not by mathematical theory, but by numerical experimentation.

Does it describe a new discovery, methodology, or synthesis of knowledge?

Figure 1: +enlarge
Click figure to enlarge and read description.
Figure 2:
Click figure to enlarge and read description.

The conclusion of this discovery, together with the follow-up paper: Huang CS, Lee CF, and Cheng AHD, "Error estimate, optimal shape factor, and high precision computation of multiquadric collocation method," Engineering Analysis with Boundary Elements, 31 [7]:614–623, 2007, essentially was that although there is no free lunch, one can indeed get a large lunch with only a little money.

This discovery may lead to new thinking in numerical methods. Most numerical methods divide the domain into elements, and use local interpolation within the elements. This method uses a global interpolation. The downside is a full matrix and high condition number, things that people tried to avoid in the past. The upside is that high accuracy can be achieved with a smaller number of nodes.

Basically, solution error is dependent on the "mesh size," h. When we put in more nodes, the spacing between the nodes, h, decreases; but computational time increases. For the finite element method (FEM), when h decreases, error decreases as h2, or, at most as h3. For the multiquadric collocation method, error decreases exponentially, e-1/h, which is much, much faster than the power-law relation.

In one example in Huang et al., we accomplished an accuracy of 10-15 with a smaller number of nodes. For FEM to accomplish such accuracy, an increase of nodes of at least 106 folds in one dimension would be needed. It is not difficult to show that the computational time needed would take much longer than the age of the Universe.

Would you summarize the significance of your paper in layman’s terms?

Engineering and science problems are often expressed in the form of mathematical equations known as partial differential equations. Our goal is to solve partial differential equations accurately and efficiently. Naturally, there will be a tradeoff: the higher accuracy we want, the more computer CPU time is needed. Based on the observation of its excellent performance, there was a certain myth developed around one numerical method, called multiquadric collocation method.

It was observed that higher and higher accuracy can be obtained by altering a constant in the interpolation function without refining the grid. The full realization of such accuracy was blocked by the computer’s inability to carry enough digits in the computation. Our work overcame this issue and found that the myth was not quite true; we do need to pay a price to reach infinite accuracy. However, the price to pay is small and we have discovered one of the most accurate numerical methods.

How did you become involved in this research and were any particular problems encountered along the way?

I have been involved in developing numerical methods for solving engineering problems since my doctoral thesis work. Particularly, I have contributed to the boundary element method (BEM). My training is in engineering. Engineers are bold; they experiment on numerical method without receiving rigorous mathematical support. Great methods were often created this way. Nevertheless, developers of numerical methods need to talk to mathematicians in order to understand the method and also to seek a rigorous mathematical foundation. Surprisingly, we rarely talk to each other. I myself have benefited from my communication with a few mathematicians.

One mathematician from whom I have gained considerable insight is Michael Golberg (formerly of the University of Nevada at Las Vegas), a coauthor of this paper. He made me aware of radial basis functions. From the literature l learned the work of Ed Kansa (formerly of the Lawrence Livermore Laboratory), another coauthor of this paper, who used multiquadric (a radial basis function) to solve partial differential equations. In fact, the method is sometimes referred to as Kansa’s method. Ed answered a lot of questions in helping me get started. Nowadays, I am relying on Zi Cai Li at the National Sun Yat-sen University, Taiwan, for my mathematical questions.

Where do you see your research leading in the future?

The findings are really exciting. There is still a long way to go to make it as competitive and popular as the FEM. Currently we still have some small mathematical gaps to fill. We need to apply the method in solving many engineering problems. Software development will be the key factor leading to widespread industrial use.

Do you foresee any social or political implications for your research?

Not immediately. But I believe that it will one day become an important branch of numerical methodology, one which offers scientific and engineering solutions which contribute to the long-term sustainability of humanity.

Alexander H.D. Cheng
Professor and Chair
Department of Civil Engineering
University of Mississippi
Oxford, MS, USA



2008 : March 2008 - Fast Moving Fronts : Alexander H.D. Cheng