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.
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?
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?
"...developers
of numerical methods need to talk
to mathematicians in order to
understand the method and also to
seek a rigorous mathematical
foundation."
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