Bulletin Spring‧Summer 1998

Research Focus study of fast algorithms in inverting a special k i nd of matrices — the Toeplitz matrices, an d has ob t a i ne d f i n a n c i a l s u p p o r t f r o m the Research Grants Council for related studies. T o e p l i tz ma t r i c es are c h a r a c t e r i z ed b y constant d i agona l entries. They occur i n ma ny applications such as the solution of p a r t i a l d i f f e r e n t i a l e q u a t i o n s , i n t e g r al equations, q u e u i ng ne t wo r k s, tim e series analysis, control theory, and more frequently i n signal and image processing. I n 1986, Prof. Gilbert Strang of the Massachusetts Institute of Technology first p r o p o s e d the fastest algorithm in inverting Toeplitz matrices: n log n operations for a Toeplitz matrix of the order n. I n 1989, Prof. Chan, i n a paper j o i n t ly prepared w i t h Prof. Strang, first s h owed mathematically that the algorithm wo r k s for a large class of Toeplitz matrices. Prof. Chan has then successfully applied the algorithm or its mo d i f i ed versions i n m a n y of the applications listed above, including a joint research project i n ground-based astronomy w i t h Prof. Robert Plemmons o f Wake Forest University, USA. Ground-based Astronomy Twinkling stars and the annoying effects of the earth's atmosphere o n l i g ht have confounded stargazers since the invention of t he telescope. C h r i s t i a n H u y g e n s , t he inventor of the p e n d u l um clock, first noticed i n the 17t h century that heavenl y bodies quivered i n telescopic v i ew through no fault of the telescope. The quivers are due i n part to the m i x i ng of w a r m and cold air layers, resulting i n changes i n air density wh i c h i n t u r n cause parts of the light waveforms to be slowed by different amounts. The light f r om distant stars travels millions of years to reach the earth but becomes blurred only i n the last f ew micro-seconds. Isaac N e w t on said i n 1704: T h e only remedy is a most serene and quiet air.' Adaptive Optics Scientists have since tried to overcome the distortion of astronomical images caused b y atmospheric turbulence. One solution is to put the telescope in space, where the Hubble space telescope n o w operates. Astronomer Horace Babcock proposed i n 1953 the concept o f adaptive optics: to use mathematics to correct the d i s t o r t i o n caused b y a t mo s p h e r ic turbulence. But his idea was not experimented w i t h until the 1970s. A n d only in the 1980s, w i t h the launch of the US Strategic Defense Initiative (SDI), or the 'Star Wars', d i d adaptive optics researchers like Prof. Plemmons gain substantial funding for their research. Adap t i ve optics can be used to improve ground-based image quality in t wo stages. First, specially designed deformabl e mirrors are operated in a closed-loop adaptive-optics system to p a r t i a l l y correct the effects of a t mo s p h e r ic t u r b u l e n c e. The p a r t i a l ly corrected image thus produced (Fig. 1 ) is then e n h a n c e d b y o f f - l i n e c o m p u t er i ma ge restoration. By analysing light returning f r o m bright stars such as Vega or artificial guid e stars created by shining a laser into the nigh t sky, the b l u r r i ng effects of the atmospheric turbulence can be obtained and expressed as a Toeplitz matrix. By inverting the matrix, the Chinese University Bulletin Spring • Summer 1998 30