Mathematics Today April 200055 idea ever devised.It will endure but get hidden deeper in the have changed,and we are all asympt tickers.When multipole meth 6.LINEAR SYSTEMS OF EQUATIONS WILL BE SOLVED IN O(N)FLOPS rom (N)to (N),giv around or tal a logarithmic factor,so how ng rur pr em e n for problems that mi all of th proximate algorithms are more robust than exact ones.and the are also often faster. to solve them in 1968 tha the O(N')ha uld b tunping time 8.BREAKTHROUGHS WILL HAVE was O(N )and sub OCCURRED IN MATRIX ent down to 2.376.How PRECONDITIONERS,SPECTRAL METHODS ct on s AND TIME STEPPING FOR PARTIAL DIFFERENTIAL EQUATIONS ake to the mos ishard ot to be optimistic abou mer ctical algorithm can ever be found,but we cer it is a jungle these days surely impre vements are in store ot know that today.A"f Spectra nethods for PDEs are nasimilar stat rema o N).and th ring it would change e As for 85I made a bet bly well i Pe r Alfeld of the sity o blems ears None ws and ev Alfeld a check for $100.Werenewed our bet,how across the range of science and engin ng.To get ar und thi ver,to 2005 ne steps are nd phy long enough important tern are thrown ay just b cause they are oo har us in the day-today 7.MULTIPOLE METHODS AND THEIR DESCENDANTS WILL BE UBIQUITOUS nd 1 9.THE DREAM OF SEAMLESS have no doubt asto what these methods are good for:they are INTEROPERABILITY WILL HAVE BEEN matrix which for O(N ACHIEVED are ofen h faster than Gaussian elimination and its rel What is curious is that Hestenes,Stiefel,Lancos and the rest for the grid g ator. ddn'hscmnin he N was too small for co the lin algebra,h s were in place.These menkne ethin bolic and numerical calculations sep arate?why can 'tour idea of the nd tools blend together int a se interoper le systen rion.Yet the made h邮r ylike this will have been couped and humans rarely catch sight of actual numbers inMathematics Today April 2000 55 idea ever devised. It will endure hut get hidden deeper in the ods, hy which I mean methods related to the recent algorithms of machine. Rokhlin and Grecngard for N-hody problems and intepal equa￾tions. Times have changed, and we are a11 asymptotickers. When multipole methods were heing invented in the 1980s, they were 6. LINEAR SYSTEMS OF EQUATIONS competitive in 2D hut not 3D. Yet Rokhlin and Greengarcl saw WILL BE SOLVED IN O(N~*') FLOPS immediately that these techniques reduced operation counts from o(N') to O(N), give or take a logarithmic factor, so how 1)cnse matrix computations as performed on machines around collld they not in the long nln? ~~~l so they will. the world typically require o(N') floating point operations - -rhe success of multipole methods will exemplify a general "flops" -where N is the dimension of the problem. This state- trend. time goes hy, large-scaIe numerical computations rely ment applies exactly for computing inverses, determinants, and on approximate algorithms, even for problems that might solutions of systems of equations, and it applies approximately in he solved exactly in a finite of for eigenvalues and singular values. But all of these prohlems in- algorithms are more robust than exact ones, and they v~lve only 0(N2) inputs, and as machines get faster, it is in- are ,lso often faster. creasingly aggravating that O(N1) operations should he needed to solve them. Strassen showed in 1968 that the o(N') harrier could he hrcached. He devised a recursive algorithm whose running time was o(N"~:'), approximately 0(N2."), and subsequent im- 8. BREAKTHROUGHS WILL HAVE provements hy Coppersmith, Winograd and others have OCCURRED IN MATRIX brought the exponent down to 2.376. However, the algorithms in question involve constants so large that they are impractical, PRECONDITIONERS, SPECTRAL METHODS and they have had little effect on scientific computing. As a re- AND TIME STEPPING FOR PARTIAL sult, the prohlem of speeding up matrix computations is viewed hy many numerical analysts as a theoretical distraction. This is a DIFFERENTIAL EQUATIONS It is hard not to he optimistic about merely technical hurdles. strange attitude to take to the most conspicuous unsolved proh- The husiness of matrix preconditioners is vitally important, hilt lem in our field! Of course, it may he that there is some reason it is a jungle these days - surely improvements are in store! why no practical algorithm can ever he found, hut we certainly Spectral methods for PDEs are in a similar state - remarkably do not know that today. A "fast matrix inverse" may he possible, powerful, hut varying awkwardly from one application to the perhaps one with complexity O(N210g N) or 0(N2loC2 N), and next. Order is needed here, and it will come. As for time- cliscovering it would change everything. stepping, this is the old prohlems of stiffness, reasonahly well in In 1985 1 made a het with Peter Alfeld of the University of hand for ODE5 hut still unsolved in a general way for PDEq. To Utah that a m;itrix algorithm with complexity 0(N2+" for any this day, the CFL restriction constrains our computations a11 E > 0 woilld he found within ten years. None was, and I gave across the range of science and engineering. To get around this We "lr het' however' to 2005* constraint, time steps are taken smaller than we would wish, and in that year I will renew it again if necessary. One morning, huge matrix prohlems are solved at great cost, and physically with luck, the headlines will appear. I think fifty years shoilld he important terms are thrown away just hecause they are too hard long enough. to implement. The CFL condition will not disappear, hut new weapons will he devised to help us in the day-to-day stri~ggle 7. MULTIPOLE METHODS AND THEIR against it. DESCENDANTS WILL BE UBIQUITOUS The conjugate gradient and Lanczos algorithms were invented :~rorlnd 1950, and their story is a curious one. Nowadays we 9. THE DREAM OFSEAMLESS have no douht as to what these methods are good for: they are matrix iterations, which for certain structured matrices hring those o(N') operation counts down to 0(N2) or even hettet. Though there arc constants hidden in the "O", these methods are often much faster than Gaussian elimination and its rela￾tivcs when N is large. What is curious is that Hestenes, Stiefel, Lanczos and the rest didn't see this coming. In the 1950s, N was too small for conju￾gate gmdients and Lnnczos yet to he competitive, hut all the mathcmatical pieces were in place. These men knew something of the convergence properties of their iterations, enough to have hecn ahle to predict that cvcntually, as machines grew faster, they must heat the competition. Yet they seem not to have made this prediction. A numerical analyst writing an essay like this one in 1960 might not have mentioned conjugate gmdients at all. It is with this history in mind that 1 mention multipole meth￾INTEROPERABILITY WILL HAVE BEEN ACHIEVED Users and onlookers complain year after year, why is so much human intervention needed to get from the whitehoard to the solution? Why does one computer program have to he written for the grid generator, another for the discretisation, and an￾other for the linear algehra, requiring interfaces a11 along the way with repeated opportunities for human error? Why are sym￾holic and numerical calculations separate? Why can't our ideas and tools hlend together into a seamless interoperahle system? Well, of course, they can, and getting there is merely an engi￾neering prohlem. Fifty years from now, the grids and the solvers will have heen coupled - and humans will more and more rarely catch sight of actual numbers in the course of doing science