Bulletin Spring‧Summer 1998

Research Focus Scientific Computing Nume r i c al analysis is the s t u dy of the mathematical theory of c omp u t a t i on w h i le scientific c o m p u t i ng is the i n t e g r a t i on of numerical analysis a nd computer technology i n s o l v i n g s c i e n t i f ic a n d e n g i n e e r i ng problems. A s a result of the great progress i n c omp u t er architecture a nd the spectacular advances i n a l g o r i t hm design i n the past f ew decades, scientific c omp u t i ng has become the t h i r d a p p r o a ch to s t u d y i n g science a n d t e c h n o l o g y, i n a d d i t i o n to t he l o n g - established t h e o r e t i c al a n d e x p e r i me n t al approaches. Its w i d e applications i n c l u de a i r c r a ft d e s i g n, w e a t h e r f o r e c a s t, a n d financial o p t i on pricing. Matrix Inversion via Fast Algorithms Scientific c o m p u t a t i on u n d e r w e nt a ma j or b r e a k t h r o u gh a b o ut 50 years ago, w h e n John v o n N e u m a n n 1 p r o v ed that the c o m p u t er he w a s b u i l d i n g c o u l d i n v e r t matrices larger than t h o u g ht possible at that time. Matrices are mathematical objects that represent the relationship between the action a n d r e a c t i on of p h y s i c a l or e c o n o m ic phenomena. By i n v e r t i ng a matrix, the action t h at causes an o b s e r v ed r e a c t i on can be k n o w n and thereby the related p h e n ome n on c an be p r e s c r i b ed or p r e d i c t e d m o r e accurately. Howe v e r, i n v e r t i ng a ma t r ix is no easy task. If the action a nd reaction are determined b y n variables (n is called the order of the matrix), then it requires about n 3 a d d i t i o n s/ s u b t r a c t i o n s / mu l t i p l i c a t i o n s / d i v i s i o n s, or s i mp ly n 3 operations, to invert the matrix. I n a w o r l d as c omp l i c a t ed as ours, it is n ot u n c o mm on to have systems described b y more than 10,000 variables, w h i ch means the i n v e r s i on i n v o l v ed w i l l require more t h an one t r i l l i on operations. Th at is a b o ut one s e c o n d 's w o r k o n t he w o r l d ' s f a s t e st computer or about half a day's w o r k o n a Pe n t i um PC. Fortunately, not all matrices are t h at c omp l i c a t e d. By e x p l o r i ng d i f f e r e nt properties i n a g i v en matrix, mathematicians can design fast algorithms for i n v e r t i ng the matrix. C o n s i d e r t he e v a l u a t i on of 2x3+2x8+2x7+2x5. O b v i o us c o m p u t a t i on requires seven operations. Howe v e r, u s i ng the distributive l aw of numbers, w h i c h one learns i n p r i ma ry school, one can obtain the s um b y evaluating 2x(3+8+7+5). It takes o n ly f o ur operations, a speedup of 75 per cent. To achieve the same a m o u nt of s p e e d up b y i mp r o v i ng computer processor design, it w i l l t a ke m o r e t h a n a y e ar of r e s e a r ch a n d development. Toeplitz Matrices P r o f. R a y m o n d H . C h a n of t h e Department of Mathematics specializes i n the 1 John von Neumann, 'Numerical Inverting of Matrices of High Order', Bulletin of theAmerican Mathematical Society, November 1947. Stargazing Through the Mathematical Telescope