1 00:00:00,900 --> 00:00:04,200 Okay. Good morning, everybody, and welcome to the last lecture. 2 00:00:04,200 --> 00:00:07,710 And thank you for your loyalty and staying through two terms of this. 3 00:00:08,550 --> 00:00:16,050 As you know, today is a little bit different in that I'm going to give a talk that I've been giving many times over the last 15 years, 4 00:00:16,050 --> 00:00:22,980 really, but it's developed over that time. And I enjoy about once a year telling people the current state. 5 00:00:27,600 --> 00:00:30,569 So the title is Who Invented the Great Numerical Algorithms? 6 00:00:30,570 --> 00:00:36,420 And maybe the first thing to say is that although that's a picture of Oxford, regrettably Cambridge would be more appropriate. 7 00:00:38,430 --> 00:00:46,680 This all began at a discussion in the Numerical Analysis Group over coffee some years ago, where in fact it was my Giles, 8 00:00:46,680 --> 00:00:56,159 I think, who was arguing persuasively that people like us academics actually didn't invent the important stuff. 9 00:00:56,160 --> 00:01:03,899 The important stuff got invented by real people out there in industry or wherever, solving real problems. 10 00:01:03,900 --> 00:01:13,500 And what academics did was tidy it up. So it occurred to us at that point, well, let's look at the data and get a sense who did invent, 11 00:01:13,500 --> 00:01:18,240 who did have the big ideas, who created the big algorithms in numerical analysis? 12 00:01:18,510 --> 00:01:29,940 And so the way this talk works is I'm going to tell you, I'm going to show you 29 pieces of paper, 29 slides, about 29 major algorithms. 13 00:01:29,940 --> 00:01:34,890 And in each case, we'll try to figure out who was the main inventor, usually two or three people. 14 00:01:35,430 --> 00:01:39,480 And what were they? Were they in academics, in industry? What was their life? 15 00:01:39,960 --> 00:01:46,590 Very hastily, of course, you can't do 29 things at leisure and then at the end come back to this question and try 16 00:01:46,590 --> 00:01:51,450 to make some generalisations about what sort of people invented the great algorithms. 17 00:01:52,330 --> 00:01:54,489 For amusement, moral, more or less. 18 00:01:54,490 --> 00:02:01,720 It's good to bear in mind the so-called Ziegler's Law of the Pandémie, which is that no scientific law is named after its original discover. 19 00:02:02,050 --> 00:02:06,340 So as we go along, you can see how valid or invalid that may be. 20 00:02:07,930 --> 00:02:16,419 So this is the list of 29 algorithms, and I've grouped them into three sections before the war, roughly speaking, after the war, 21 00:02:16,420 --> 00:02:26,590 and then sort of in the time of my career, roughly speaking, I stop at 2000 and at the end I'll have a word to say about things more recent than 2000. 22 00:02:28,760 --> 00:02:31,700 Okay. So let's begin with 1940. It's chronological. 23 00:02:31,970 --> 00:02:38,900 And the very first thing we'll talk about is Newton's method for nonlinear equations, which we use all the time in this course. 24 00:02:38,900 --> 00:02:42,920 We've used it a lot. Very major idea in numerical computing. 25 00:02:43,190 --> 00:02:48,740 Well, there's Newton, of course. We all know him. And there's no doubt he was one of the key people involved with this. 26 00:02:49,700 --> 00:02:54,440 Not much to say that you don't already know. He was one of the greatest thinkers of all time. 27 00:02:54,770 --> 00:03:03,380 He was an eccentric, annoying academic at Trinity College who spent many years at Trinity, thoroughly an academic for most of his career. 28 00:03:03,980 --> 00:03:08,390 Certainly at the time that he did his legendary work, he was an academic at Trinity. 29 00:03:08,810 --> 00:03:16,100 Eventually he became a celebrity and master of the Mint and moved to London and did all sorts of governmental things. 30 00:03:16,310 --> 00:03:22,459 But that was after his research period. It is somebody we don't know as much about. 31 00:03:22,460 --> 00:03:26,420 Of course, we've all heard the expression Newton Roughton. But who was this guy? 32 00:03:26,630 --> 00:03:35,170 Well, it turns out he was a mathematician, more or less of Newton's time, who worked with Newton and was one of the people in the calculus wars. 33 00:03:35,180 --> 00:03:39,440 You know, there were limits and Newton who should get the credit for calculus. 34 00:03:39,950 --> 00:03:48,380 This became a very ugly chapter in intellectual history, with the British being particularly ugly in their fanatical defence of Newton. 35 00:03:49,400 --> 00:03:52,459 Apparently Rapson was one of the key guys doing that. 36 00:03:52,460 --> 00:03:57,140 The history of flux fluctuations. You can imagine which side of the argument that was on. 37 00:03:58,860 --> 00:04:00,960 Simpson, I think is a great hair figure. 38 00:04:00,990 --> 00:04:07,530 He was really a very major numerical person with a fine mind, very creative, who did a number of important things. 39 00:04:07,770 --> 00:04:15,690 You'll notice in the comments here that Newton didn't use Newton's method, but really only for very low order scalar polynomials. 40 00:04:16,630 --> 00:04:24,550 It was Simpson who moved to non polynomial problems and also who treated systems of equations. 41 00:04:24,820 --> 00:04:29,200 So Simpson somehow saw the bigger vision of what Newton had done. 42 00:04:31,770 --> 00:04:37,530 Who was Simpson. He was at the Royal Military Academy in Woolwich, which is London, more or less. 43 00:04:37,530 --> 00:04:41,820 And I guess that makes him an academic with an interest in military applications. 44 00:04:43,870 --> 00:04:47,770 Now least square fitting is the second on the list. Another huge topic. 45 00:04:48,100 --> 00:04:52,300 It's, among other things, the foundation of the whole field of statistics, you might say. 46 00:04:53,380 --> 00:05:00,070 This has in common with the first topic that it was founded in great acrimony, this time by Gauss and Legend. 47 00:05:00,640 --> 00:05:04,420 So just like Newton and Leyden to co-invented the calculus, 48 00:05:04,720 --> 00:05:10,270 gauss and the genre independently invented least squares, fitting the genre was the first to publish. 49 00:05:10,270 --> 00:05:14,499 But Gauss may have had the idea first. Who knows? They got in a big fight. 50 00:05:14,500 --> 00:05:20,960 Another ugly episode. Gauss, like Newton, is, of course, one of the great figures of all time. 51 00:05:21,010 --> 00:05:27,310 He did everything in physics and mathematics. He's a mathematician and also a physicist of the highest order. 52 00:05:28,300 --> 00:05:34,900 His career, as you know, was quite spectacular as a teenager, sort of in a sixth form college, as you might say. 53 00:05:35,290 --> 00:05:44,010 He did unbelievable things. You know, the binomial theorem, the quadratic, reciprocity, arithmetic, geometric means an incredible guy. 54 00:05:44,020 --> 00:05:48,430 And in 1795, he would have been 18 years old when he invented least squares fitting. 55 00:05:48,850 --> 00:05:53,590 He was very interested in orbits of asteroids and so on, and that was one of his interests. 56 00:05:54,130 --> 00:06:00,400 So he was an academic, though very much involved in the practical scientific problems of his day. 57 00:06:01,850 --> 00:06:10,009 Alexandra, another well known mathematician. Of course, he was active during the difficult times in French history, the revolution. 58 00:06:10,010 --> 00:06:16,680 And after that, you can see. Well, at 1805 in France, that's the Year of Trafalgar, right? 59 00:06:16,690 --> 00:06:24,300 You can just imagine how complicated things were. He invented leaf squares also in connection with commentary orbits. 60 00:06:25,050 --> 00:06:32,350 For many years this was the picture of Alexandra. And then four or five years ago, thanks to the miracle of the web, 61 00:06:32,890 --> 00:06:37,960 somebody noticed that there were two different people called Alexandra, and they both had the same picture. 62 00:06:38,290 --> 00:06:43,620 There's a politician and a mathematician. And if you looked at either one, you would be pointed to this picture. 63 00:06:43,630 --> 00:06:47,470 So one of them must be wrong. And it turned out the mathematician was wrong. 64 00:06:47,860 --> 00:06:54,940 So far as I'm aware, the only known image of Alexandra is this caricature from some collection of caricatures of mathematicians. 65 00:06:58,380 --> 00:07:06,330 Now Gaussian elimination for linear systems of equations, another absolutely fundamental algorithm that one is certainly an example of Ziegler's law. 66 00:07:06,330 --> 00:07:15,000 It's ancient. It was described by the Chinese in the third century A.D. but even then it was old news to the Chinese, I think. 67 00:07:15,270 --> 00:07:20,970 So the idea of eliminating variables, I guess, is a pretty natural one, and it goes way back. 68 00:07:21,210 --> 00:07:26,820 As soon as people start having coupled systems of equations, of course, they're going to try to eliminate variables. 69 00:07:27,180 --> 00:07:36,660 So the history there is very murky. Gauss himself was one of the players, of course, though not particularly the pivotal one. 70 00:07:36,670 --> 00:07:39,370 He, as far as I know, only did symmetric systems. 71 00:07:40,060 --> 00:07:49,420 The non symmetric case was seemingly written down first by Jacobi, though that doesn't mean he was the first to have thoughts in those directions. 72 00:07:50,260 --> 00:07:53,499 Jacoby was, as I've mentioned, one of my great heroes. 73 00:07:53,500 --> 00:07:57,130 I think he's an extraordinary person who only lived a few years. 74 00:07:57,160 --> 00:08:02,139 Look at that. An academic at Berlin and Königsberg died in his mid-forties, 75 00:08:02,140 --> 00:08:10,030 but in that time wrote a dozen papers in both pure and applied mathematics that changed all sorts of things. 76 00:08:12,820 --> 00:08:13,930 Now go quadrature. 77 00:08:14,990 --> 00:08:23,380 That's a beautiful, powerful idea for integrating functions, the benchmark against which all other methods of integration are measured. 78 00:08:24,310 --> 00:08:29,490 This is the cleanest example I know of. A counterexample I know to Stigler is law. 79 00:08:29,500 --> 00:08:36,940 It really was invented by Gauss. I don't think anyone before Gauss did this at all because it's a tricky idea. 80 00:08:36,940 --> 00:08:43,960 It's not something you would invent so casually. So Gauss did it out of the blue in 1814, when he was 37 years old. 81 00:08:44,530 --> 00:08:45,940 He published that paper. 82 00:08:47,260 --> 00:08:54,219 He did it, by the way, via continued fractions, which is a technique that was big in the 19th century and nowadays we don't know much about. 83 00:08:54,220 --> 00:08:57,190 It's considered now a kind of an odd way to approach things. 84 00:08:57,430 --> 00:09:04,450 And in fact, it was Jacoby who a few years later turned to Gauss Quadrature into an application of orthogonal polynomials, 85 00:09:04,630 --> 00:09:12,310 which is how everyone perceives it now. So notice these ideas we're talking about are absolutely fun fundamental ideas. 86 00:09:12,310 --> 00:09:20,290 In Numerics, we've had Newton's method and Gauss Quadrature and linear systems of equations by Gaussian elimination least squares. 87 00:09:20,620 --> 00:09:23,740 These are crucial ideas for mathematics and science. 88 00:09:27,040 --> 00:09:30,879 What about formula for odds, which we've certainly talked about in this course? 89 00:09:30,880 --> 00:09:35,690 Adams Formulas? Well, certainly one of the key people there was Adams. 90 00:09:35,710 --> 00:09:39,370 But before him, for the first order formula at least, is Euler. 91 00:09:39,730 --> 00:09:47,590 And Euler, we know, was another one of these astonishing figures like Newton and Gauss, to whom we owe much of modern mathematics. 92 00:09:48,470 --> 00:09:51,470 Euler lived at also a complicated time. 93 00:09:51,470 --> 00:09:57,080 He was Swiss from Basel, but he spent his career in Prussia and in St Petersburg. 94 00:09:58,320 --> 00:10:02,270 His he had some rather good mentors. 95 00:10:02,270 --> 00:10:07,670 So one of the protectors, whenever we you call them, one of them was Catherine the Great and another was Frederick the Great. 96 00:10:07,700 --> 00:10:11,330 So that's pretty good to have on your resume. Not in the letters of recommendation. 97 00:10:11,900 --> 00:10:15,020 Actually, the letters might not have been so good. He annoyed them a little bit. 98 00:10:16,530 --> 00:10:24,840 But anyway, Euler had this astonishing academic career, one of the most prolific mathematicians of all time, a great master of mathematics. 99 00:10:26,490 --> 00:10:29,880 Adams was a Cambridge man. He spent his life at Cambridge. 100 00:10:29,910 --> 00:10:37,740 You can see he was born in 1819. And then when he was 24 or so, he was the top student in his year at Cambridge. 101 00:10:39,310 --> 00:10:43,030 That's fourth I think I mentioned this in one of my lectures was in the same year at 102 00:10:43,030 --> 00:10:47,480 Cambridge and where Adams was the senior wrangler back fourth was the second wrangler. 103 00:10:47,740 --> 00:10:51,890 But that's fourth scores, and the exams were about half as high as Adams. 104 00:10:52,210 --> 00:10:58,330 So Adams was a true genius, one of these extraordinary people that people are still talking about years later. 105 00:10:58,900 --> 00:11:04,570 So he had this fantastic career at Cambridge, very much involved in astronomical questions. 106 00:11:04,570 --> 00:11:08,050 And a mathematician fundamentally, when he was quite young, 107 00:11:08,470 --> 00:11:13,330 he studied the perturbations of the orbits of Uranus and predicted there must be another planet out there. 108 00:11:13,630 --> 00:11:19,090 But as the story goes, the Astronomer Royal refused to point the telescopes in the right direction. 109 00:11:19,390 --> 00:11:22,570 So in the end, the French discovered Neptune instead of the Brits. 110 00:11:24,350 --> 00:11:29,180 He has a good reputation for having declined honours. He was offered a knighthood and said no. 111 00:11:29,390 --> 00:11:33,470 He was offered the Astronomer Royal Post and said No. Sounds good to me. 112 00:11:34,720 --> 00:11:37,810 Now back fourth is a much less important figure overall. 113 00:11:37,960 --> 00:11:41,640 But we've all heard of Adams best fourth methods. Now, who was him? 114 00:11:41,650 --> 00:11:46,480 He. Well, he was at the Royal Military Academy in Woolwich, also. 115 00:11:46,750 --> 00:11:50,470 And it seems he worked on these methods 30 years later. 116 00:11:50,770 --> 00:11:56,530 But those were maybe the first publications. It's not clear Adams published anything in the 1850s. 117 00:11:57,440 --> 00:12:03,469 And although he was a ballistics expert and you think ADAMS mapping odds ballistics, 118 00:12:03,470 --> 00:12:07,700 it seems that it was actually shapes of drops that were his initial application. 119 00:12:07,970 --> 00:12:14,340 I'm a little unclear on that. Now, the other great classic formula for Ode to Ease is running a cut of formulas. 120 00:12:15,280 --> 00:12:20,230 And these date to about 50 years later three Germans basically it seems wrong 121 00:12:20,350 --> 00:12:25,480 and Hein and Qatar were very much involved at the turn of the 20th century. 122 00:12:27,900 --> 00:12:32,549 Like Adam's formulas. As I say at the top, these are generalisations of Euler. 123 00:12:32,550 --> 00:12:37,200 Euler, the first order Euler formula is both in atoms and the wrong kind of formula, if you like. 124 00:12:37,410 --> 00:12:40,350 It's when you go to higher orders that the two diverge. 125 00:12:41,100 --> 00:12:47,219 So I wrote this paper in 1895 and I, as I've mentioned to you in the class, he's another one of my heroes. 126 00:12:47,220 --> 00:12:50,910 He did so many fundamental things. We'll see his name again in a moment. 127 00:12:51,720 --> 00:12:59,190 Holy. I don't know much about he guess. I guess he was in theoretical mechanics, which is what they call the applied mathematics and move days. 128 00:13:00,000 --> 00:13:04,140 And then Qatar is well known for the current condition in aerodynamics. 129 00:13:04,920 --> 00:13:11,020 So he was a fluid person and a mathematician. And then after that, 130 00:13:11,020 --> 00:13:21,219 a lot of people were interested von Mises the this is a great machination also wrote a major paper on wrong a kind of method in the modern era. 131 00:13:21,220 --> 00:13:26,890 It's John Butcher who's still alive in New Zealand. He put them on a sound mathematical footing. 132 00:13:27,220 --> 00:13:33,250 So throughout the last 40 years, really, John Butcher has been the man in the cut the area. 133 00:13:33,730 --> 00:13:35,320 But no way that he invent them. 134 00:13:38,480 --> 00:13:45,290 And I think this is the last of my pre 1940 topic finite differences for PDAs, which we've seen a lot of in this course. 135 00:13:45,770 --> 00:13:53,000 It's pretty hard to say who invented that. But there are some remarkable pre-computer people and I mentioned. 136 00:13:53,950 --> 00:14:01,259 Three groups there. Richardson and Southwell were both British mathematicians. 137 00:14:01,260 --> 00:14:06,520 Engineers who? Use these so-called relaxation methods. 138 00:14:06,850 --> 00:14:10,870 Before there were machines. It's just amazing. We've talked a bit about Richardson. 139 00:14:11,050 --> 00:14:17,320 You did a problem related to him on the last assignment. He was a remarkable, very interesting figure in all sorts of ways. 140 00:14:18,670 --> 00:14:21,760 Southwell is the only Oxford contribution to this talk. 141 00:14:21,880 --> 00:14:27,310 He was a legendary engineer at Oxford, apparently a fantastic lecturer. 142 00:14:27,310 --> 00:14:33,490 People found him extraordinary. So this is Richardson there and Southwell there. 143 00:14:35,980 --> 00:14:39,490 Friedrichs and LaVey wrote this legendary paper in the 1920s, 144 00:14:39,490 --> 00:14:46,090 which for theoretical purposes more or less founded the Leapfrog Method and moreover, the idea of stability analysis. 145 00:14:46,420 --> 00:14:50,200 They didn't interpret that in terms of things blowing up on a computer, of course. 146 00:14:50,530 --> 00:14:56,379 Nevertheless, they had the key idea. And then when computers came along, many people got involved. 147 00:14:56,380 --> 00:14:59,680 Of course, too. Two of the key ones were Von Neumann and LAX. 148 00:15:00,100 --> 00:15:04,389 Von Neumann, of course, much older than LAX, a very sadly died. 149 00:15:04,390 --> 00:15:12,490 Young von Neumann, as you know, was one of the great mathematician scientists of all time, certainly of the 20th century. 150 00:15:12,820 --> 00:15:16,030 You can see that he, like Jacoby, died in his forties. 151 00:15:16,480 --> 00:15:19,510 Peter LAX is still with us. He's won the Abel Prize and so on. 152 00:15:19,810 --> 00:15:26,200 So von Neumann had this young kid, Peter Laks, working with him at Los Alamos during the war. 153 00:15:26,230 --> 00:15:30,700 Basically, Laks went on to have an academic career at the Crown Institute. 154 00:15:31,030 --> 00:15:35,679 He won all the prizes. Von Neumann was very much involved in government work. 155 00:15:35,680 --> 00:15:40,000 He was, for example, on the Atomic Energy Commission for a couple of years. 156 00:15:43,120 --> 00:15:46,720 Okay. So then you have the war and post-war era. 157 00:15:51,230 --> 00:15:54,680 So the next one I'd like to mention is floating point arithmetic. 158 00:15:55,130 --> 00:15:58,170 Now, most people don't know who invented that. 159 00:15:58,190 --> 00:16:01,390 If you ask the typical numerical analyst who invented that, they don't know. 160 00:16:01,400 --> 00:16:08,690 I didn't know when I started to work on this topic. But it turns out it was invented very clearly at sea, not by Babbage, 161 00:16:08,690 --> 00:16:15,110 as you might have guessed, but by Conrad Sousa, who was engineer, mathematician in Berlin. 162 00:16:15,680 --> 00:16:23,590 Very interesting, unusual person. So during the Nazi era, he had this company in Berlin called Sousa Operator Bow, 163 00:16:23,600 --> 00:16:30,110 and they built a succession of computers which were incredibly modern in concept, obviously not in hardware. 164 00:16:30,740 --> 00:16:39,080 But you can see, for example, I mentioned there is 22 bit floating point binary arithmetic, 14 bits for the fraction, eight bits for the exponent. 165 00:16:39,260 --> 00:16:43,159 It's just the way computers work now. Although now we can afford more bits. 166 00:16:43,160 --> 00:16:48,319 Of course. The clock speed was one hertz. It was programmable. 167 00:16:48,320 --> 00:16:50,960 Although you didn't store the program, the only stored the data. 168 00:16:51,500 --> 00:16:57,890 This particular machine of his that I mentioned there was destroyed in the air raid in 1945. 169 00:16:59,500 --> 00:17:07,480 I don't know that much about that. It seems that incredibly he wasn't so much wrapped up in the Nazi stuff. 170 00:17:08,680 --> 00:17:13,510 The line, they say, is that the Nazis did not appreciate how important computers were. 171 00:17:13,870 --> 00:17:17,810 How true that is, I don't know. He then lived for a long time. 172 00:17:17,830 --> 00:17:25,720 No, this until 1995. In the late forties, early fifties, he was a name that people paid attention to when they were recreating computers. 173 00:17:26,080 --> 00:17:29,080 But then he lived on and on. And he was a fantastic artist. 174 00:17:29,090 --> 00:17:33,370 So here's an example of one of his watercolours. Very remarkable man, I think. 175 00:17:36,640 --> 00:17:40,960 Lyons, one of the key ideas for representing functions and surfaces. 176 00:17:42,130 --> 00:17:45,340 So this is one that clearly did have some roots in industry. 177 00:17:47,570 --> 00:17:53,300 Strangely in the car industry. So you see two of the key early names are the custodial and busier. 178 00:17:53,660 --> 00:17:59,180 And these were both French people involved with cars at C Tire and at Renault. 179 00:18:00,260 --> 00:18:03,110 The Casio was basically a mathematician and a physicist. 180 00:18:03,110 --> 00:18:09,890 Bazzi seems to have been an engineer so far as I know DeCastro is still alive, but I don't know if that's true. 181 00:18:11,620 --> 00:18:17,410 One of the sad things over the years with me giving this talk is that every time I give it, a few more people have died. 182 00:18:17,920 --> 00:18:21,400 Now most of them are gone. But Carl, the book is very much with us. 183 00:18:22,270 --> 00:18:31,420 Schonberg was this remarkable man from Romania, from the intellectual elite in Romania, if you like, who then came to the US, as many people did. 184 00:18:31,780 --> 00:18:37,810 He was at Chicago and Harvard and Princeton and twice more Pennsylvania, eventually Wisconsin. 185 00:18:38,200 --> 00:18:42,370 And he wrote some key early papers on aeroplanes and a book on Sloan. 186 00:18:43,180 --> 00:18:47,350 Carl de Boer was then a very major mathematician who. 187 00:18:48,560 --> 00:18:55,520 What's the first mathematician, I guess you'd say, to really bring blinds into the modern era somehow? 188 00:18:56,090 --> 00:19:03,170 Interestingly, he although he's very much an academic for most of his life, at a key stage, he was working at General Motors. 189 00:19:03,530 --> 00:19:05,870 So he was born in what became East Germany. 190 00:19:05,870 --> 00:19:17,450 And he came over here at age 22, over here to the west, and made his life in America and certainly made it big. 191 00:19:18,020 --> 00:19:22,130 He's now actually living in retirement in the San Juan Islands near Seattle. 192 00:19:24,670 --> 00:19:33,370 Monte Carlo simulation. Well, if you're a good test taker, one thing you know about Monte Carlo is whether it was invented in Europe or America. 193 00:19:33,820 --> 00:19:37,660 Well, obviously Europe, because if it were America, it would be Las Vegas method. 194 00:19:37,750 --> 00:19:40,870 Right. So it's a European who's going to have invented this? 195 00:19:41,620 --> 00:19:50,380 And these are the three key names. So you have Stanislaw Ulam, who is a Pole, who came to the US and became a very patriotic American. 196 00:19:52,320 --> 00:19:57,840 Very much a mathematician, a pure mathematician even, and yet was heavily involved with Los Alamos. 197 00:19:58,080 --> 00:20:02,190 And he was one of the key people who figured out how to make a hydrogen bomb work. 198 00:20:02,670 --> 00:20:10,560 So there's really an exceptional case of a mathematician who would have thought of himself as very pure doing very major applied work. 199 00:20:12,770 --> 00:20:18,589 John Barnes. Meanwhile him again, a very major guy in mathematics and physics and everything in between. 200 00:20:18,590 --> 00:20:22,370 He spans the pure applied spectrum better than almost anybody. 201 00:20:22,970 --> 00:20:25,280 His base was Princeton, I guess you'd say. 202 00:20:25,310 --> 00:20:32,720 He was born in Hungary, but came to America when he was in his twenties and then was a key person in the Manhattan Project. 203 00:20:34,270 --> 00:20:37,660 And Nicholas Metropoulos was a physicist, a Greek American. 204 00:20:37,990 --> 00:20:43,750 And he has this complicated career where he was at Chicago and Los Alamos and kept going back and forth. 205 00:20:43,780 --> 00:20:53,830 Obviously, there were two places important to him, very much wrapped up in the military industrial complex, I guess you'd say the official invention. 206 00:20:54,280 --> 00:20:59,380 A lot of these things were officially invented after the war. You never quite know what happened during the war. 207 00:21:00,040 --> 00:21:06,190 But anyway, the first papers are in 1947, very much in the realm of nuclear technology. 208 00:21:07,150 --> 00:21:14,040 And then this major paper by Ulam and Metropolis and 49 other physicists very much involved Fermi and Whitmire. 209 00:21:17,770 --> 00:21:21,670 Monte Carlo. Things just keep growing in importance. Stochastic issues. 210 00:21:23,860 --> 00:21:26,470 The Simplex algorithm for linear programming. 211 00:21:26,620 --> 00:21:33,129 This is the problem where you have a lot of variables and a lot of linear function of them and a lot of constraints. 212 00:21:33,130 --> 00:21:37,060 And you want to find the optimum. Well, the two. 213 00:21:38,070 --> 00:21:47,430 People who invented linear programming, at least if maybe not quite the simplex algorithm are Kontorovich in the Soviet Union and Danzig in the USA. 214 00:21:47,850 --> 00:21:49,800 Very much war stories. 215 00:21:50,610 --> 00:22:00,330 Kontorovich was in Leningrad St Petersburg and he was an academic mathematician but much involved with the planning of production. 216 00:22:00,600 --> 00:22:07,530 Patrick Farrell isn't here, I think, but he was. He pointed me to something on the web about the problem of getting plywood to the right 217 00:22:07,530 --> 00:22:13,080 place at the right time in order to fight off the Finns during the early stages of the war. 218 00:22:14,460 --> 00:22:21,630 Kontorovich had these remarkable ideas about linear programming, and if you've read this novel, read plenty. 219 00:22:21,640 --> 00:22:26,160 He's one of the characters in Red Plenty about the Soviet vision. 220 00:22:26,160 --> 00:22:33,540 You know, we're so steeped in the sort of post-Soviet post-Soviet era that we we kind of forget the beautiful, 221 00:22:33,540 --> 00:22:39,150 noble thought that many people had, which was that it makes sense to do things optimally. 222 00:22:39,300 --> 00:22:45,670 Right. These guys had the idea that. Capitalism is a mess because nothing is optimal. 223 00:22:45,970 --> 00:22:51,700 Whereas if you really do your mathematics right, you can have all the right inputs in all the right places at the right time, 224 00:22:51,700 --> 00:22:54,909 and the outputs will come out optimal at some level. 225 00:22:54,910 --> 00:22:59,020 That's right. It leaves out enough that at some level it's also deeply wrong. 226 00:22:59,320 --> 00:23:04,390 But there was something truly beautiful there. And Kontorovich was part of that tradition. 227 00:23:06,640 --> 00:23:11,410 George Danzig was very much in the Western tradition. 228 00:23:11,740 --> 00:23:17,379 Now, here's a guy who was a major academic, a brilliant mathematician, truly brilliant. 229 00:23:17,380 --> 00:23:24,050 He was a very, very special man. During the war when he's very young, you know, 1941. 230 00:23:24,050 --> 00:23:29,240 So what is he, 27? He was head of the combat analysis branch of the U.S. Air Force. 231 00:23:29,270 --> 00:23:39,290 What does that mean? One of the amazing things looking through the history of the war is how young the scientists were who had this incredible impact. 232 00:23:39,620 --> 00:23:43,919 For example, the. The Manhattan Project. 233 00:23:43,920 --> 00:23:49,650 The head of the theoretical division was Hans Baker, and he was the senior guy who bossed around the younger figures. 234 00:23:49,890 --> 00:23:51,720 He was like 37 years old. 235 00:23:52,020 --> 00:24:01,110 It's just astonishing that such key things were done by people in their twenties and thirties on the scientific side of the war effort. 236 00:24:02,520 --> 00:24:08,490 Now you can see if you get the War Department Exceptional Civilian Service Medal, you're probably doing some good things. 237 00:24:08,760 --> 00:24:13,560 A couple of years later, he got his Ph.D. and then in 47 outcomes, the simplex algorithm. 238 00:24:14,070 --> 00:24:18,330 Kontorovich didn't quite write down the simplex algorithm, but it's all in the same territory. 239 00:24:18,510 --> 00:24:22,620 Dan did the expression linear programming came along a year later, 240 00:24:22,800 --> 00:24:28,740 and then the original think tank was the Rand Corporation in Santa monica, California. 241 00:24:28,980 --> 00:24:35,760 The phrase think tank sort of came from that one. And Danzig was a key person in that original think tank. 242 00:24:36,270 --> 00:24:40,770 So here's a man who's very much in the military industrial complex, if you like. 243 00:24:41,010 --> 00:24:44,160 But his foundation was always academic. 244 00:24:44,700 --> 00:24:48,390 He was at Berkeley for a few years and then Stanford for 40 years. 245 00:24:48,420 --> 00:24:53,460 So very major figure making Stanford so great in areas of operations research. 246 00:24:57,100 --> 00:25:01,960 Now conjugate gradients and land growth iterations. This is all about iterative linear algebra. 247 00:25:02,140 --> 00:25:06,320 We've talked about that and you know, it begins in 1952. 248 00:25:06,340 --> 00:25:10,749 That's the magical year. And these three people were clearly the key. 249 00:25:10,750 --> 00:25:14,950 People have finished. And Stifel wrote the paper on conjugate gradients. 250 00:25:15,160 --> 00:25:20,290 But at the same time, Lunchbox was writing his papers on very closely related techniques. 251 00:25:20,710 --> 00:25:25,320 Now, one chose was a Hungarian Jew. He was born Lavi and changed his name to Lantos. 252 00:25:26,650 --> 00:25:31,480 He worked with Thayer and Einstein, eventually moved to the West. 253 00:25:32,110 --> 00:25:37,600 He went to America and was, of course, in the war era, too. 254 00:25:38,410 --> 00:25:42,729 I believe he was a communist. And so things got a little bit hot for him in the fifties. 255 00:25:42,730 --> 00:25:46,660 So he left the U.S. during the McCarthy era and ended up in Dublin. 256 00:25:46,990 --> 00:25:52,810 And there's a very nice video of him from the 1970s talking about mathematics. 257 00:25:53,110 --> 00:25:59,960 So if you Google, you can find him on YouTube and check. I was an American at the University of Chicago. 258 00:26:00,560 --> 00:26:06,830 He spent some time at the legendary Institute of Numerical Analysis in Los Angeles, part of the National Bureau of Standard. 259 00:26:07,070 --> 00:26:11,000 That was an exciting place for a few years where numerical things were happening. 260 00:26:12,220 --> 00:26:16,120 Stiefel was an eminent professor at the EPA in Zurich, 261 00:26:16,570 --> 00:26:23,830 and he was he's very well known as a pure mathematician and geometry, as well as for conjugate gradients. 262 00:26:24,040 --> 00:26:30,790 Also a physicist. He looked at that intense look. He reminds me of like The Third Man by Orson Welles or something. 263 00:26:34,310 --> 00:26:40,430 Fortran. Anyone know who invented Fortran? It's another one man thing. 264 00:26:41,780 --> 00:26:46,760 John Backus. He invented Fortran, and it's an amazing story. 265 00:26:47,000 --> 00:26:54,120 So most of the people I've been telling you about are among the great academic geniuses of all time. 266 00:26:54,140 --> 00:26:59,930 In many cases, these are truly extraordinary people who take all the boxes of intellectual achievement. 267 00:27:00,200 --> 00:27:04,730 Now, Backus was a little bit more human than that. It seems that his early years were a bit of a mess. 268 00:27:05,570 --> 00:27:09,830 Somehow, at around late twenties, I guess he found him or mid-twenties. 269 00:27:09,830 --> 00:27:13,819 He found himself at IBM, which was an old company. 270 00:27:13,820 --> 00:27:22,630 But of course its great era was just beginning. And then he had this idea that maybe it would make sense to have a programming language. 271 00:27:22,870 --> 00:27:27,220 And he persuaded the managers at IBM to fund this. So they built a little team. 272 00:27:27,970 --> 00:27:31,460 And nearly three years later, released Fortran. 273 00:27:31,480 --> 00:27:32,770 It's an incredible story. 274 00:27:33,430 --> 00:27:39,370 We all think of Fortran as having been there forever and come, you know, it must have come from a team of thousands or something. 275 00:27:39,370 --> 00:27:44,620 But I think this was a little group working for a few years at IBM and out it came. 276 00:27:44,800 --> 00:27:52,180 And of course it changed the world with not quite literally the first programming language, but it was the one that changed the world. 277 00:27:52,990 --> 00:27:57,370 He got the National Medal of Science, the Turing Award, all of these big gongs later on. 278 00:27:59,860 --> 00:28:03,670 But anyway, he spent his career, I guess, at IBM. 279 00:28:06,790 --> 00:28:14,770 Stiff Odds solvers. We've talked about that a bit. What do you do when you have different timescales in a time dependent problem? 280 00:28:14,950 --> 00:28:19,899 That's a problem, an issue that keeps getting bigger and bigger because in multi physics, if you like, 281 00:28:19,900 --> 00:28:25,480 multi scale physics these days, you so often need to couple together different time scales. 282 00:28:25,750 --> 00:28:33,559 So this is at the heart of many, many things. And. The two people who put this problem on the map were Curtis and Hirschfeld there. 283 00:28:33,560 --> 00:28:39,410 And they were a pair of chemists, and this was in their great paper in 1952, integration of this equation. 284 00:28:40,310 --> 00:28:47,030 So these were pretty remarkable people. Curtis was an eminent chemist who did government work during the war. 285 00:28:48,380 --> 00:28:53,540 And then Hirschfeld, who was truly a major figure in American chemistry. 286 00:28:53,750 --> 00:28:58,460 So you can see, like so many of these people, he was an academic with war involvement. 287 00:28:58,760 --> 00:29:04,380 So he was at Los Alamos leading a group. And like so many people, he wasn't very old. 288 00:29:04,400 --> 00:29:11,880 You see, he's a group leader at age 32. And then he was the chief phenomenon of the bikini bottom test. 289 00:29:11,950 --> 00:29:15,370 That's pretty amazing for a guy of a 35. 290 00:29:17,150 --> 00:29:24,860 So obviously he and Curtis, he will have been involved with very applied problems then this great paper of theirs in 1952. 291 00:29:25,010 --> 00:29:31,160 And later he got into the National Academy of Science, the National Medal of Science, which is the top thing in the US, basically. 292 00:29:32,000 --> 00:29:35,059 Then the academic involvement came a little bit later. 293 00:29:35,060 --> 00:29:43,280 German Dahlquist, who we've mentioned, wrote his great paper in 1963, and that sounded the subject of stiffness as a mathematical discipline. 294 00:29:43,430 --> 00:29:48,050 In fact, Curtis and Hirschfeld had made a key mathematical mistake in their paper. 295 00:29:49,130 --> 00:29:55,940 And then Geer was the person who made the subject famous at a practical level, beginning the software stiff solver. 296 00:29:56,780 --> 00:30:02,059 Gear, by the way, was an academic for most of his career, but at this time of the work, 297 00:30:02,060 --> 00:30:04,880 he was very much involved in the Argonne National Lab in the US. 298 00:30:05,870 --> 00:30:13,430 And then after some decades he moved to NBC, which is a company, and so far as I know, he's now retired. 299 00:30:13,880 --> 00:30:18,470 He's British, by the way. I didn't say that here, but a Brit who ended up in the US. 300 00:30:21,690 --> 00:30:31,890 Now what about finite elements? This is one where that famously has an industrial connection, although a little murkier than you might imagine. 301 00:30:32,870 --> 00:30:40,520 In some sense. The first paper on the subject is by Richard Courant, but it really didn't have much impact. 302 00:30:40,790 --> 00:30:49,790 It's now recognised as a foundational paper. Courant was a remarkable man, so he was a German who was the head of the institute in Göttingen, 303 00:30:50,030 --> 00:30:55,879 where Hilbert had been an extraordinary situation but then had to leave during the 304 00:30:55,880 --> 00:31:01,130 Nazi era and came to the US and founded the current institute at New York University, 305 00:31:01,280 --> 00:31:04,610 which became really the great applied mathematics place in the U.S. 306 00:31:06,670 --> 00:31:13,300 But there were many aeronautical engineer who were involved, and some names are Martin and Turner and Irons and Kelsey and Poppy. 307 00:31:14,770 --> 00:31:20,370 So a lot of these ideas were bubbling around. Now, who actually invented the term and sort of pulled it together? 308 00:31:20,920 --> 00:31:23,920 These two people in 1960 seem to have been key. 309 00:31:23,950 --> 00:31:31,000 So John, our guy, Chris, was a Greek who spent his career in Germany and he wrote this key book in 1960. 310 00:31:31,240 --> 00:31:37,770 And Ray Plus, an American at Berkeley also was involved in 1960. 311 00:31:37,780 --> 00:31:43,480 So 1960 would often be regarded as the sort of the date it all came together in finite elements. 312 00:31:43,720 --> 00:31:49,300 But with these earlier roots classes, the remarkable man, another winner of the National Medal of Science, 313 00:31:49,510 --> 00:31:52,930 you get the impression from this talk that everybody gets the National Medal of Science. 314 00:31:52,930 --> 00:31:55,150 But that's not true. It's hard to get that. 315 00:31:56,350 --> 00:32:02,500 He's actually best known not for having invented finite elements, but for his work on earthquake related engineering. 316 00:32:04,420 --> 00:32:08,170 Other key old figures are babushka ends and Kasich. 317 00:32:08,380 --> 00:32:13,900 Babushka is still alive. This great man from Czechoslovakia who moved to the US in 1968. 318 00:32:14,200 --> 00:32:19,240 I think Kasich died a few years ago. He I guess was Polish, but his career in Wales. 319 00:32:22,610 --> 00:32:27,800 Now in numerical linear algebra, most of the great algorithms have an orthogonal aspect, 320 00:32:28,490 --> 00:32:32,930 and that all happened in the sixties, basically at the late fifties and sixties. 321 00:32:33,140 --> 00:32:36,230 And I think the three key names are givens and householder. 322 00:32:36,230 --> 00:32:44,900 And so Givens in 1958 introduced really the first numerical technique that was orthogonal, given the rotations. 323 00:32:45,230 --> 00:32:49,280 Householder then made it much bigger with his givens reflectors. 324 00:32:50,690 --> 00:32:54,020 So somehow householder was the person who put this stuff on the map. 325 00:32:54,380 --> 00:33:00,410 And then Jane Garland saw the much wider picture of all of numerical linear algebra and its pervasive 326 00:33:00,410 --> 00:33:06,530 importance throughout science and the pervasive importance of orthogonal methods throughout linear algebra. 327 00:33:07,160 --> 00:33:16,070 So Ghalib was the big figure in this era, though maybe Householder was the one who first put together the functionality. 328 00:33:16,790 --> 00:33:20,960 An early paper of globes that was major was linearly squared. 329 00:33:21,280 --> 00:33:28,340 It's now so obvious to us that you can do linearly squares with orthogonal matrix algorithms, but that wasn't obvious back then. 330 00:33:28,580 --> 00:33:32,810 People would do the normal equations and factor those somehow non orthogonal. 331 00:33:34,580 --> 00:33:41,330 So Ghalib was born on February 29th. He would be 84 years old on Monday. 332 00:33:45,920 --> 00:33:51,050 What about the QR algorithm? One of the most beautiful success stories in all of numerical analysis. 333 00:33:51,350 --> 00:33:58,580 This is the one that has most perfectly become a black box that everybody knows and loves and uses without caring what's inside it. 334 00:34:00,250 --> 00:34:05,530 So I think these are the four key names route is has her invented a thing called the ELA algorithm, 335 00:34:05,530 --> 00:34:08,320 which was the non orthogonal version of the QR algorithm? 336 00:34:08,530 --> 00:34:13,780 So in some sense that was the basic idea of factoring one way and then recombining the factors in the 337 00:34:13,780 --> 00:34:22,450 other direction and then I guess independently a.k.a a woman in Soviet Union and John Francis in England. 338 00:34:23,970 --> 00:34:27,770 Worked on the orthogonal version of that, which became the QR algorithm, 339 00:34:28,080 --> 00:34:35,490 and Francis in particular introduced the bells and whistles we now know so well the the crucial idea of shifting. 340 00:34:36,120 --> 00:34:44,309 You need to take your matrix and first try diagonals it or make it in Heisenberg form, do some shift chase bulges. 341 00:34:44,310 --> 00:34:50,400 All that stuff is very much rooted with Francis and he was close to Wilkinson, 342 00:34:50,400 --> 00:34:56,880 who then became the great figure in the area, wrote his magnum opus in 1965. 343 00:34:57,300 --> 00:35:05,430 So certainly Wilkinson is the one we can credit for making eigenvalue solution such a well advanced subject. 344 00:35:06,630 --> 00:35:12,990 Wilkinson is a very interesting man. He was a wunderkind at Cambridge and very young when the war started. 345 00:35:13,270 --> 00:35:16,590 But so at age 2021, he was working in the war effort. 346 00:35:17,100 --> 00:35:21,960 Then he became Turing's right hand man on the pilot ace computer at the National Physical Laboratory. 347 00:35:22,710 --> 00:35:29,970 But Turing didn't get along well with the National Physical Laboratory, so he went off to Manchester, where he eventually died. 348 00:35:30,870 --> 00:35:36,390 Wilkinson had a great career at the National Physical Laboratory and, as I say, wrote this book. 349 00:35:36,570 --> 00:35:37,709 He got all the prizes. 350 00:35:37,710 --> 00:35:46,890 The Turing Award, in particular for computer science, is only rarely given to numerical people, but he and Cahun and Backus are three at. 351 00:35:50,170 --> 00:35:54,070 The Fast Fourier transform. This has one of the most complicated histories. 352 00:35:56,110 --> 00:36:01,130 There's no doubt where that name comes from. It comes from Cooley in Tukey in 1965. 353 00:36:01,150 --> 00:36:09,309 So Julian Tuki. So here's maybe the one case where the names I put in big letters were certainly not the first inventors. 354 00:36:09,310 --> 00:36:13,390 The first inventor seems to have been Gauss in 1805. No impact at all. 355 00:36:13,630 --> 00:36:16,690 But then it was invented over and over again. It seems wrong. 356 00:36:16,690 --> 00:36:21,280 And my hero invented it. Thomas Mann shows good. 357 00:36:21,280 --> 00:36:29,080 Another hero. Wheeler Gentlemen. Many people seem to have noticed that you can do a clever recursion and improve and square to enlarge in. 358 00:36:30,750 --> 00:36:36,960 But somehow it was in 1965 that this all got named and changed the world. 359 00:36:37,650 --> 00:36:44,820 Turkey was one of the major statisticians of the 20th century, a larger than life figure physically as well as mentally. 360 00:36:45,060 --> 00:36:54,210 Extraordinary man, a prolific, amazing man who was an academic but heavily involved with non-academic things. 361 00:36:55,170 --> 00:37:00,990 So he founded the Statistics Department at Princeton, but was always at Bell Labs and other consulting places. 362 00:37:01,320 --> 00:37:06,030 Richard Garwin is a physicist with a major involvement with the H-bomb still around, I think. 363 00:37:06,330 --> 00:37:10,650 And for example, he was interested in detection of nuclear tests. 364 00:37:11,650 --> 00:37:18,690 I guess that would now be North Korea's nuclear test. James Cooley, so far as I know, is still around. 365 00:37:18,690 --> 00:37:22,559 And he was at IBM. I not I don't know much about him. 366 00:37:22,560 --> 00:37:28,380 I don't think he's such a major figure or certainly the heavy hitter here is Tukey and Garwin is also very well. 367 00:37:31,630 --> 00:37:37,209 Kwasi Newton methods. As I guess I briefly mentioned last term, 368 00:37:37,210 --> 00:37:42,760 are a way for doing Newton's method without doing all the linear algebra involved 369 00:37:42,760 --> 00:37:47,590 in solving setting up and solving a big system of equations at every step. 370 00:37:48,100 --> 00:37:51,760 So this was a beautiful idea, came along in the sixties and seventies. 371 00:37:51,940 --> 00:37:55,540 The first paper in 1959 by William Davidson. 372 00:37:56,320 --> 00:38:01,330 So he was a physicist at Chicago, an academic who spent his career at Haverford. 373 00:38:01,360 --> 00:38:06,220 He was a Quaker. That paper didn't get accepted and he got mad. 374 00:38:06,230 --> 00:38:08,540 So he he he put it in a drawer. 375 00:38:08,540 --> 00:38:17,060 And then 30 years later, when the Journal of Optimisation was founded, they pulled it out of the door and published evidence paper at last. 376 00:38:17,790 --> 00:38:21,750 Michael Power was for years the dominant numerical analyst in this country. 377 00:38:22,260 --> 00:38:29,999 He just died last year. And he was a key people or a key person all along in these early development droid in another key person. 378 00:38:30,000 --> 00:38:36,690 And Fletcher, who's still with us, another key person. So Royden had a complicated career. 379 00:38:36,690 --> 00:38:43,260 I guess he was in English Electric during the crucial years, but then later was an academic and spent a number of years in Italy. 380 00:38:44,010 --> 00:38:46,890 Roger Fletcher has basically been at the University of Dundee, 381 00:38:47,130 --> 00:38:52,860 but in the early days was at Harwell, the nuclear lab where he and Powell worked together. 382 00:38:57,640 --> 00:39:05,650 So that brings us to the post, the modern era, shall we say, or the early modern era, whatever you want to call preconditioning. 383 00:39:06,190 --> 00:39:14,900 Key idea in solving system of equations. Many people claim the credit, but I think the one who is the really important figure is Vandervoort. 384 00:39:15,380 --> 00:39:21,950 He wasn't the first to have the idea at all, maybe, but he's the one who put it on the map and thought it's pervasive, important. 385 00:39:22,190 --> 00:39:28,520 Moreover, he invented incomplete factorisation, which remains one of the key preconditions. 386 00:39:28,880 --> 00:39:33,530 So he's a remarkable man, still very much with us, relatively young. 387 00:39:34,070 --> 00:39:38,510 Also like Conrad Sousa, an excellent artist, an extraordinary artist. 388 00:39:38,510 --> 00:39:44,560 And there is one of many of his work. So he was very much an academic. 389 00:39:46,130 --> 00:39:51,200 Spectral methods for solving differential equations we've talked about the phrase comes from 390 00:39:51,200 --> 00:39:56,929 Steve Moore that he invented the phrase spectral methods and his post-doc David Gottlieb. 391 00:39:56,930 --> 00:40:01,850 In the early years, the two of them sort of initiated this subject that was at MIT. 392 00:40:02,630 --> 00:40:05,660 They were academics interested, especially in fluid mechanics. 393 00:40:06,530 --> 00:40:10,220 Orszag then went on to a number of places and then died a couple of years ago. 394 00:40:10,760 --> 00:40:20,060 Gottlieb was an Israeli who spent his career in Israel and the U.S., and that was at Brown for many, many years, but also at Tel Aviv. 395 00:40:24,250 --> 00:40:29,170 I think you probably know who invented MATLAB since I mentioned it fairly often that Cleave Mueller. 396 00:40:29,710 --> 00:40:34,450 Cleave Mueller is very much with us. Born in 39. So he's from Utah. 397 00:40:35,670 --> 00:40:45,090 And grew up as a very smart kid, went to Caltech, did very well and an academic, but with involvement in other things. 398 00:40:45,570 --> 00:40:48,510 Argonne National Laboratory, again, was a key thing for him. 399 00:40:48,750 --> 00:40:53,770 So notice after Caltech, he did his Ph.D. at Stanford and then went to Michigan and New Mexico. 400 00:40:53,970 --> 00:40:58,620 And it was when he was a professor in New Mexico that he did the MATLAB stuff. 401 00:40:59,130 --> 00:41:05,700 So MATLAB came from his academic years, but then later he joined a company that Jack Little had found. 402 00:41:07,260 --> 00:41:10,680 So notice at the bottom matlab is two thirds as old is FORTRAN. 403 00:41:11,160 --> 00:41:15,209 Maybe you think of them both as infinitely old, so you don't distinguish them. 404 00:41:15,210 --> 00:41:21,510 But for people of my generation we think of Fortran as having always been there and MATLAB is sort of the new upstart. 405 00:41:21,540 --> 00:41:27,010 Well, that's not true. It. Multi grid methods. 406 00:41:27,310 --> 00:41:33,010 One of the major technologies for solving the discrete equations associated with differential equations. 407 00:41:33,880 --> 00:41:36,970 They were invented by Federico in the Soviet Union. 408 00:41:36,970 --> 00:41:42,190 At least a two grid method at first. And then, voila, with another key name. 409 00:41:42,190 --> 00:41:48,070 I don't know so much about Federico. Aki Grant is the person who made them big in the West. 410 00:41:48,280 --> 00:41:51,850 Well, indeed, anywhere. I don't think Federico stuff led to so much. 411 00:41:52,150 --> 00:41:56,380 But Brandt learned about it from Federico, so that was not an independent discovery. 412 00:41:56,590 --> 00:42:02,110 But Brandt enlarged the field extraordinarily. And then Hotchpotch was an independent discovery, 413 00:42:02,110 --> 00:42:09,370 a German academic who independently invented air guitar for fire and then later realised it was the same as multiple. 414 00:42:09,670 --> 00:42:12,819 So another academic. This is no longer up to date. 415 00:42:12,820 --> 00:42:21,740 He's now retired from Leipzig. I Tripoli arithmetic which we use all the time. 416 00:42:21,740 --> 00:42:27,080 You you've never used anything else? Probably. This is the standard way we represent numbers on a computer. 417 00:42:27,620 --> 00:42:34,250 Well, that comes from a committee, but there's no doubt that the driving force behind the committee was William Cohan. 418 00:42:34,520 --> 00:42:39,079 So he's an extraordinary man at the University of California at Berkeley, 419 00:42:39,080 --> 00:42:44,959 Canadian originally, but he spent his career at Berkeley, been there for many, many years. 420 00:42:44,960 --> 00:42:46,760 He's another winner of the Turing Award. 421 00:42:47,210 --> 00:42:52,790 He saw the importance of standardisation, of floating point arithmetic, and he banged heads together until it happened. 422 00:42:53,330 --> 00:43:00,020 A remarkable success story. Not a symmetric cry laugh iterations. 423 00:43:00,020 --> 00:43:08,480 Well, in 1952 we had conjugate gradients and lunchbox, and in the early seventies those took over a lot of computational science. 424 00:43:08,960 --> 00:43:15,140 The non symmetric story is more complicated. The roots are equally old, but it didn't become important as quickly. 425 00:43:16,420 --> 00:43:19,540 So for example, our A.D. is also from back in the fifties. 426 00:43:19,840 --> 00:43:24,400 The first sort of practical use seems to have been at the Shell Petroleum Company. 427 00:43:24,580 --> 00:43:27,729 But I don't know anything about Vincent Yusef. 428 00:43:27,730 --> 00:43:35,430 Saad, an academic at Yale at that time, was a major, major person, and Hank Vandervoort another major person. 429 00:43:35,450 --> 00:43:45,429 So Guimaraes comes from new facade. Basically, SAB and Jacoby Davidson come from Vandervoort, and a third very major person is Dan Sorensen, 430 00:43:45,430 --> 00:43:49,300 who at that time was at the Argonne National Lab and then later Rice. 431 00:43:50,190 --> 00:43:59,460 He with his collaborators, invented, implicitly restarted Arnold which is the standard way we now try to find eigenvalues of big matrices. 432 00:43:59,730 --> 00:44:03,600 So Air Pack and the MATLAB I command coming from third. 433 00:44:07,570 --> 00:44:13,750 Interior point methods for optimisation. So the simplex method works on the outside of a region of feasibility. 434 00:44:13,960 --> 00:44:19,120 Interior point methods follow a curve on the inside, and there's no doubt that that was. 435 00:44:19,390 --> 00:44:25,180 That made the headlines because of Karmakar Narendra karmakar in 1984. 436 00:44:25,390 --> 00:44:29,049 Now, he wasn't the first to have ideas along these lines. 437 00:44:29,050 --> 00:44:34,060 There were important precursors. Some of them, like Hutcheon, were much more theoretical. 438 00:44:34,570 --> 00:44:37,600 Others like Margaret Wright. We're focusing on other aspects. 439 00:44:38,350 --> 00:44:43,090 But it was Karmakar who realised that this could really have huge practical importance. 440 00:44:43,420 --> 00:44:51,520 And in 1984, he at Bell Labs annoyed a lot of people by making outrageous claims and refusing to release the software. 441 00:44:51,550 --> 00:44:57,640 It was a very touchy time in optimisation, but an extraordinary contribution. 442 00:44:57,850 --> 00:45:03,100 So he did his degrees in electrical engineering and then was at Bell Labs when this happened. 443 00:45:03,310 --> 00:45:14,340 And he's now in India and I'm not sure what he's doing. The fast multiple method is a fast way for solving systems. 444 00:45:14,700 --> 00:45:20,759 I could accelerate a little bit and this comes from Green Card and Rocklin, as everybody knows, a remarkable pair of people. 445 00:45:20,760 --> 00:45:26,489 Rocklin is a Russian who came to the U.S. in mid-career, now at Yale, so an academic. 446 00:45:26,490 --> 00:45:33,320 But he was at Exxon at a crucial time. Leslie Green Garden is very much an academic at Courant Institute. 447 00:45:33,330 --> 00:45:36,390 Basically, though, he's now running the Simon Centre for Data Analysis. 448 00:45:36,660 --> 00:45:43,050 I say they both have eminent fathers as well. Rockman father also called Vladimir, was one of the major Soviet mathematicians. 449 00:45:43,530 --> 00:45:46,710 Green Garden father is a Nobel Prize winner in physiology. 450 00:45:48,630 --> 00:45:51,900 I think. No, I guess I have to, ma'am. Wavelets. 451 00:45:53,940 --> 00:45:58,200 Very important technology in signal processing to tell the truth. 452 00:45:58,230 --> 00:46:01,590 I'm not sure they're that important in numerical computation. 453 00:46:02,940 --> 00:46:07,620 I'm not sure it's a huge, crucial fact in computation more broadly. 454 00:46:07,950 --> 00:46:13,620 But whether it's major in, you know, sort of my kind of numerical computation, I'm not so sure on that. 455 00:46:14,430 --> 00:46:19,650 But it's a beautiful, powerful thing in signal. The roots tend to be francophone. 456 00:46:20,520 --> 00:46:24,059 John Marlay is one of the key ones. Other names you may recognise. 457 00:46:24,060 --> 00:46:28,080 And then Ingrid DAVIES, she is the person who put them on the map in 1988. 458 00:46:28,290 --> 00:46:31,770 She's interesting, very much an academic, but with links at AT&T. 459 00:46:32,340 --> 00:46:37,440 A physicist by training but also a mathematician in her early years for publications are in physics. 460 00:46:37,680 --> 00:46:43,230 But then she moved into mathematics at Princeton. And though that's out of date, she's now at Duke. 461 00:46:46,020 --> 00:46:53,910 Finally, automatic differentiation, a way to compute derivatives not by finite differences, but by other computational methods. 462 00:46:55,580 --> 00:47:04,070 That idea has been invented in some sense many times, but I think it came together and became important because of Andrea's remark. 463 00:47:04,460 --> 00:47:12,740 I guess I haven't really put dates there, but this would have been in the 1980s, I guess, when he was at Argonne National Laboratory. 464 00:47:12,980 --> 00:47:19,820 I should get the dates there. So he was at Argonne and he saw how to connect, spark, linear algebra to aid. 465 00:47:20,090 --> 00:47:21,770 And from then it just took off. 466 00:47:22,650 --> 00:47:30,120 He was in Germany for most of his career at the Humboldt University, but he's now retired from there and moved to Ecuador. 467 00:47:33,700 --> 00:47:39,910 Okay. So now we come to the end where I try to make some generalisations about what we've seen. 468 00:47:41,570 --> 00:47:45,650 So first of all, about the people who invented these great algorithms. 469 00:47:45,860 --> 00:47:49,640 Let's ask. Well, there they are. Those are the names that I put in boldface. 470 00:47:50,300 --> 00:47:55,490 So of course, I'm omitting a lot of precursors here. But these are the ones that I've selected. 471 00:47:57,460 --> 00:48:04,000 So let's ask Firth, who is an engineer. Well, I think those people were engineers. 472 00:48:04,000 --> 00:48:08,020 So they're are an important subset, but it's a reasonably small subset. 473 00:48:08,020 --> 00:48:13,530 One, two, three, four, five, six, seven. Who is a physicist. 474 00:48:15,800 --> 00:48:20,630 This is another important subset, slightly larger. I've given three people half a half billing. 475 00:48:20,690 --> 00:48:24,200 So obviously Gauss and Newton, I've called half physics, 476 00:48:24,200 --> 00:48:29,420 half mathematics because I think none of them would be pleased to be called just one and not the other. 477 00:48:32,620 --> 00:48:37,029 Who was a chemist. Well, Curtis and her father. 478 00:48:37,030 --> 00:48:41,709 I'm not aware of others on this list. Of course, the list has all sorts of biases. 479 00:48:41,710 --> 00:48:46,900 So you can tell me of some I may have admitted. Who was a mathematician. 480 00:48:48,450 --> 00:48:55,590 Well, most of them were mathematicians. Now, the way I like this up is I call computer scientists and statisticians mathematicians, 481 00:48:55,830 --> 00:48:58,530 because most of them would be proud to be called mathematicians. 482 00:48:58,860 --> 00:49:03,990 I certainly have not called physicists mathematicians because most of them would be mad to be called mathematicians. 483 00:49:05,820 --> 00:49:10,590 But this is very striking, isn't it? Who was a professor. 484 00:49:12,290 --> 00:49:20,000 Almost everybody. There are a few weird cases in England where people that would be called professors in other countries didn't have that title here. 485 00:49:20,210 --> 00:49:26,570 And I really mean an academic, of course. So it's very striking how almost everybody was a professor. 486 00:49:26,780 --> 00:49:34,620 But that may not be all they were. On the other side who had major involvement with government or industry. 487 00:49:34,620 --> 00:49:38,160 And there, again, it's a huge number. This is very striking to me. 488 00:49:38,850 --> 00:49:45,770 Something like 3/5 of these people. I don't just mean that they picked up a little money on the side doing consulting. 489 00:49:45,770 --> 00:49:49,700 I mean, major, major involvements with serious applications. 490 00:49:52,230 --> 00:49:56,820 Who was Griffith? Well, pretty good for the population. 491 00:50:00,520 --> 00:50:03,909 With gear. Oh, yeah. Gear. Yeah. Who was German? 492 00:50:03,910 --> 00:50:07,020 Swiss. Austrian. Well, it's always impressive. 493 00:50:07,030 --> 00:50:12,710 The. That's history. A lot of them. Who was born in the only a few. 494 00:50:14,270 --> 00:50:19,000 Who ended up in the U.S. in more. How old were they? 495 00:50:19,540 --> 00:50:26,290 So, of course, everybody with white hair is very interested in the question of how well, what's the upper limit of doing interesting things. 496 00:50:28,780 --> 00:50:34,180 So if you look at the numbers in each case, I've tried to estimate how old they were when they did their legendary work. 497 00:50:34,720 --> 00:50:38,380 And a few cases, you see several numbers for people who have appeared more than once. 498 00:50:39,600 --> 00:50:43,020 I find looking at those numbers that what's striking is the variety. 499 00:50:43,020 --> 00:50:50,030 You have everything from 20 to 60, basically many people, very young, many people maybe not so young. 500 00:50:51,890 --> 00:50:59,630 Now in numerical analysis, there's a prize given every couple of years called the Fox Prize, and the last two winners were from Oxford. 501 00:51:00,050 --> 00:51:04,720 You have to be 31 or less. So all of these people are eligible. 502 00:51:05,890 --> 00:51:09,490 Most of them, of course. Well, many of them died before there was a Fox Prize. 503 00:51:10,030 --> 00:51:16,479 But I don't think any of them actually won the Fox Prize, although Green Guard was of a generation where he might have. 504 00:51:16,480 --> 00:51:20,320 But I guess he did mentor something and. 505 00:51:22,490 --> 00:51:26,209 Newton was pretty good at age 27. He could have won. Actually, no. 506 00:51:26,210 --> 00:51:32,790 You have to give a good talk. I'm not sure Newton could give it. So back to the opening question. 507 00:51:34,210 --> 00:51:37,500 You had these two models of where great algorithms come from. 508 00:51:37,500 --> 00:51:42,930 One is academics doing their thing, and the other is real people confronting real problems. 509 00:51:43,350 --> 00:51:52,920 And I believe that the answer is kind of a remarkable combination, that in most cases, these people are academic mathematicians. 510 00:51:53,220 --> 00:51:55,950 They really are academic and they really are mathematicians. 511 00:51:56,220 --> 00:52:02,910 But at the same time, they have a level of involvement with applications that transcends the usual transcends. 512 00:52:02,910 --> 00:52:10,920 For example, anything I've ever done, I've never had anything approaching that kind of involvement with reality that many of these people have had. 513 00:52:11,160 --> 00:52:17,730 Now, of course, partly it's hard to disentangle it from the war because that was such a transformative experience at a key time. 514 00:52:19,910 --> 00:52:23,720 So then the question is, what's the first great numerical algorithm of the 21st century? 515 00:52:23,900 --> 00:52:27,620 Now, as I say, I first gave this talk at the turn of the 21st century. 516 00:52:28,310 --> 00:52:31,490 So the way I ended it then was with this picture. 517 00:52:32,180 --> 00:52:36,860 But, you know, now we're 16 years into the 21st century, so I don't have any more slides. 518 00:52:36,860 --> 00:52:40,760 But let me just tell you what I think the area would be. 519 00:52:41,840 --> 00:52:45,140 Whether there's one or two or three algorithms to talk about, I don't know. 520 00:52:45,320 --> 00:52:53,300 But I think the huge new thing in the last 15 years has to do with big data and randomness. 521 00:52:53,720 --> 00:52:56,900 The use of randomness, I think it was essentially nowhere. 522 00:52:56,900 --> 00:53:03,410 Well, Monte Carlo, we mentioned, but it has now become so much more important things to do with compressing data, 523 00:53:03,500 --> 00:53:07,970 huge matrices, low rank compression, sampling them in random dimensions. 524 00:53:08,180 --> 00:53:10,700 That is everywhere. It's very, very important. 525 00:53:10,940 --> 00:53:18,620 So with without a doubt, there's at least one more entry in this list potentially from the last 15 years, maybe two or three. 526 00:53:19,010 --> 00:53:22,970 And I would like to hear your views on that, if you have you. Okay. 527 00:53:23,180 --> 00:53:23,780 Thank you very much.