Stargazing through the Mathematical Telescope


Scientific Computing

Numerical analysis is the study of the mathematical theory of computation while scientific computing is the integration of numerical analysis and computer technology in solving scientific and engineering problems. As a result of the great progress in computer architecture and the spectacular advances in algorithm design in the past few decades, scientific computing has become the third approach to studying science and technology, in addition to the long-established theoretical and experimental approaches. Its wide applications include aircraft design, weather forecast, and financial option pricing.

Matrix Inversion via Fast Algorithms

Scientific computation underwent a major breakthrough about 50 years ago, when John von Neumann1 proved that the computer he was building could invert matrices larger than thought possible at that time. Matrices are mathematical objects that represent the relationship between the action and reaction of physical or economic phenomena. By inverting a matrix, the action that causes an observed reaction can be known and thereby the related phenomenon can be prescribed or predicted more accurately.
However, inverting a matrix is no easy task. If the action and reaction are determined by n variables (n is called the order of the matrix), then it requires about n3 additions/subtractions/multiplications/divisions, or simply n3 operations, to invert the matrix. In a world as complicated as ours, it is not uncommon to have systems described by more than 10, 000 variables, which means the inversion involved will require more than one trillion operations. That is about one second's work on the world's fastest computer or about half a day's work on a Pentium PC. Fortunately, not all matrices are that complicated. By exploring different properties in a given matrix, mathematicians can design fast algorithms for inverting the matrix.
Consider the evaluation of 2x3+2x8+2x7+2x5. Obvious computation requires seven operations. However, using the distributive law of numbers, which one learns in primary school, one can obtain the sum by evaluating 2x(3+8+7+5). It takes only four operations, a speedup of 75 per cent. To achieve the same amount of speedup by improving computer processor design, it will take more than a year of research and development.

Toeplitz Matrices

Prof. Raymond H. Chan of the Department of Mathematics specializes in the study of fast algorithms in inverting a special kind of matrices—the Toeplitz matrices, and has obtained financial support from the Research Grants Council for related studies. Toeplitz matrices are characterized by constant diagonal entries. They occur in many applications such as the solution of partial differential equations, integral equations, queuing networks, time series analysis, control theory, and more frequently in signal and image processing. In 1986, Prof. Gilbert Strang of the Massachusetts Institute of Technology first proposed the fastest algorithm in inverting Toeplitz matrices: n log n operations for a Toeplitz matrix of the order n. In 1989, Prof. Chan, in a paper jointly prepared with Prof. Strang, first showed mathematically that the algorithm works for a large class of Toeplitz matrices. Prof. Chan has then successfully applied the algorithm or its modified versions in many of the applications listed above, including a joint research project in ground-based astronomy with Prof. Robert Plemmons of Wake Forest University, USA.

Ground-based Astronomy

Twinkling stars and the annoying effects of the earth's atmosphere on light have confounded stargazers since the invention of the telescope. Christian Huygens, the inventor of the pendulum clock, first noticed in the 17th century that heavenly bodies quivered in telescopic view through no fault of the telescope. The quivers are due in part to the mixing of warm and cold air layers, resulting in changes in air density which in turn cause parts of the light waveforms to be slowed by different amounts. The light from distant stars travels millions of years to reach the earth but becomes blurred only in the last few micro-seconds. Isaac Newton said in 1704: 'The only remedy is a most serene and quiet air.'

Adaptive Optics

Scientists have since tried to overcome the distortion of astronomical images caused by atmospheric turbulence. One solution is to put the telescope in space, where the Hubble space telescope now operates. Astronomer Horace Babcock proposed in 1953 the concept of adaptive optics: to use mathematics to correct the distortion caused by atmospheric turbulence. But his idea was not experimented with until the 1970s. And only in the 1980s, with the launch of the US Strategic Defense Initiative (SDI), or the 'Star Wars', did adaptive optics researchers like Prof. Plemmons gain substantial funding for their research.
Adaptive optics can be used to improve ground-based image quality in two stages. First, specially designed deformable mirrors are operated in a closed-loop adaptive-optics system to partially correct the effects of atmospheric turbulence. The partially corrected image thus produced (Fig. 1) is then enhanced by off-line computer image restoration. By analysing light returning from bright stars such as Vega or artificial guide stars created by shining a laser into the night sky, the blurring effects of the atmospheric turbulence can be obtained and expressed as a Toeplitz matrix. By inverting the matrix, the distorting effects of the earth's atmosphere can be diminished and a clearer image of the celestial object is available (Fig. 2).

Sample Before Processing Sample After Processing
Figure 1:An image of an ocean reconnaissance satellite observed by a ground-based imaging system Figure 2: The restored image after matrix inversion

The second stage of the process may seem like a straightforward matrix inversion problem. What makes the difference is the order of the Toeplitz matrix, or the value of n. The value of n may range from 60,000 for low resolution images to over a million for high resolution images. As atmospheric effects are changing almost every second, the inversions of matrices have to be done continuously. Given that a generic matrix inversion algorithm for a matrix of order n requires about n3 operations, zillions and zillions of computations will have to be done and done fast in order to deblur the images. But this is beyond the capability of even the fastest computer available. Prof. Chan and his partners have developed a specific fast algorithm for these Toeplitz matrices that reduces the amount of computation to a manageable level, as a result of which reasonably high-speed computers can solve the problems within a short time.

Telescopes with Adaptive Optics

Equipped with these techniques, telescopes are able to see 50 to 150 times more clearly. The researchers envisage that the mathematics of adaptive optics will one day allow ground-based telescopes to possess the same imaging power as the Hubble. Adaptive optics can also be used to keep better tabs on spy satellites, protect space shuttle crews and satellites from orbiting space junks, and produce highly accurate laser-guided weapons. In a formal hearing organized by the US House Appropriation Committee into the 1997 budget requests, Prof. Plemmons explained the research results and their applications to support the budget request made by the US Department of Defense. At the conclusion of Plemmons' testimony, Bill Young, chair of the Subcommittee on National Security, remarked, 'You have now answered my main question, as to why the Department of Defense should be funding research in the mathematical sciences.'2
Prof. Raymond Chan was awarded a Leslie Fox Prize on Numerical Analysis (1989) by the Institute of Mathematics and Applications, UK, and the Feng Kang Prize in Scientific Computing (1997) by the Chinese Academy of Sciences in recognition of his contribution to fast algorithms for Toeplitz systems. His former Ph.D. student, Michael Ng, working with Prof. Chan and Prof. Plemmons on image restoration problems, was also awarded an Honorable Mention in the Householder Prize Competition held in Switzerland in 1996.


Prof. Raymond H. Chan obtained his B.Sc. degree from The Chinese University of Hong Kong, and his M.Sc. and Ph.D. degrees from the Courant Institute of Mathematical Sciences at New York University. He had taught at the University of Massachusetts at Amherst, the University of Hong Kong, and the Hong Kong University of Science and Technology before joining his alma mater as a senior lecturer in 1993. He was the vice-president of the Hong Kong Mathematical Society from 1994 to 1996.
Prof. Chan is an associate director of the University's Institute of Mathematical Sciences, a chief editor of the Asian Journal of Mathematics, and an editorial board member of four other journals.

1 John von Neumann, 'Numerical Inverting of Matrices of High Order', Bulletin of the American Mathematical Society, November 1947.
2 See 'What Does the Government Get for Its investment in Basic Research', Society of Industrial and Applied Mathematics (SIAM) News, June 1996