Math Invented for Moon Landing Helps Your Flight Arrive on Time | Hacker News Reader

Math Invented for Moon Landing Helps Your Flight Arrive on Time

nasa.gov

117 pointswglb38 comments

About the significance of the Schmidt-Kalman filter (from a related abstract):

>In most target tracking formulations, the tracking sensor location is typically assumed perfectly known. Without accounting for navigation errors of the sensor platform, regular Kalman filters tend to be optimistic (i.e., the covariance matrix far below the actual mean squared errors) ... The Schmidt-Kalman filter (SKF) does not estimate the navigation errors explicitly but rather takes into account the navigation error covariance provided by an on-board navigation unit in the tracking filter formulation. By exploring the structural navigation errors, the SKF is not only more consistent but also produces smaller mean squared errors than regular Kalman filters.

Kalman filters are useful for much more than that :)

I'm barely acquainted with them, but this[1] seems to be a good introduction that doesn't shove math under the rug.

Schmidt's modification of Kalman filter allowed for a practical implementation of it on the Apollo computer. The history and the motivation for the changes are excellently described in a survey paper co-authored by Schmidt himself in 1985[2]:

>Dr. Kalman's original formulation would have required an on-board crew to make a continuous sequence of optical measurements equally spaced in time throughout the lunar mission, an impractical scenario. Therefore, to implement our measurement and course-correction schedule, the original formulation had to be revised.

This paper, [2], offers amazing historical tidibtis (especially relevant on HN): computational challenges, project running 6 months behind schedule, why it was better than least-squares methods (computation time!), numerical stability, implementation details that allowed for use of floats (single precision) vs. double precision, FORTRAN implementation vs. specialized hardware, etc.

I find it amazing that nearly 60 years later, we are still dealing with the same issues in machine learning and high-performance computing: from single vs. double precision and numerical stability down to, well, using Kalman filters - and yes, FORTRAN and specialized hardware. And projects running behind schedule.

(Last time I had to touch FORTRAN code was.. a month ago. Also guess what powers all your shiny NumPy/SciPy computations: a lot of FORTRAN.)

[1]https://towardsdatascience.com/kalman-filter-an-algorithm-fo...

[2]https://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/198600...

> I find it amazing that nearly 60 years later, we are still dealing with the same issues in machine learning and high-performance computing: from single vs. double precision and numerical stability down to, well, using Kalman filters - and yes, FORTRAN and specialized hardware. And projects running behind schedule.

On the other hand, I don't find this amazing at all. Numerics are fundamentally difficult, the people who worked on them at the beginning were very smart. Projects have always been behind schedule. It doesn't surprise me at all that we've been stuck on at least a local maxima on many of these things....

The amazing part to me was that people had reached those maxima so fast: by 1960, barely after the computers have been invented, and with such limited resources.

Perhaps think about it this way: precisely because we had such limited resources at the time, smart people were highly motivated to find those (local?) maxima. These days in many contexts it is easier to say "eh, good enough" and move on to the next thing.

To add to this topic: the fast hardware adder, patented by IBM in 1957, now in some forms present in all fast CPUs, was already invented by Charles Babbage between 1820 and 1830, before the middle of 19th (!) century as he designed his mechanical computing "difference" engine:

https://en.wikipedia.org/wiki/Carry-lookahead_adder

Apparently, he was proud of that invention, only almost nobody was able to appreciate it then.

From "Passages from the Life of a Philosopher (1864) by Charles Babbage"

https://en.wikisource.org/wiki/Passages_from_the_Life_of_a_P...

"The first idea was, naturally, to add each digit successively. This, however, would occupy much time if the numbers added together consisted of many places of figures.

The next step was to add all the digits of the two numbers each to each at the same instant, but reserving a certain mechanical memorandum, wherever a carriage became due. These carriages were then to be executed successively. "

A 3D model:

https://www.youtube.com/watch?v=B2EDE8Srdcw

by the author of:

https://en.wikipedia.org/wiki/The_Thrilling_Adventures_of_Lo...

FORTRAN is immensely better than most its critics are aware, and it god a lot of solutions right. Already since around 1950 it had the format specifications:

https://www.fortran.com/FortranForTheIBM704.pdf

quite similar to those used later in C (since around 1970) and even Python (since around 1990) and Java... since version 5.0 in 2004.

Moreover, the format specifications were a part of the language, not "just a string that was traditionally not checked" as in C.

We should sit down and chat about FORTRAN II with its three-number if statements. I spent a lot of years in that particular village, and was sufficiently frustrated with its limitations that it drove me to a career in writing compilers.

In addition to the language you note stealing the format idea, you need to include Lisp.

> was sufficiently frustrated with its limitations that it drove me to a career in writing compilers.

I'm genuinely interested!

> FORTRAN II with its three-number if statements

The IBM FORTRAN for 704 (from 1956) had them already, as in the link already posted. Yes, all these labels were definitely annoying, the researchers did work on ALGOL already two years later. FORTRAN itself also improved over time, but for most of the decades the sources were indeed ugly compared to the printed ALGOL in the papers (the implementations were often something else) and all the languages inspired by that. The problem with the numerical labels was recognized even in 1958. Sadly the first standard that allowed not writing them was Fortran 8x (later know as 90):

https://www.sciencedirect.com/science/article/pii/0010465587...

"Since 1979, the Fortran standardization committee, X3J3, has been labouring over a draft for the next version of the standard. Its initial intention of publishing this draft in 1982 was hopelessly optimistic, and at best it may be ready this year" (1987)

It eventually became ISO in 1991.

At that time, on the microcomputers, Turbo Pascal was already 8 years old. It was the fastest to develop and really convenient. But if you wanted really heavy numerics, you also had to buy additional hardware and... probably use FORTRAN.

http://www.classiccmp.org/transputer/documentation/microway/...

So back in the heyday of Fortran II, it did work on smaller computers.

One key frustration I had with Fortran II was that you couldn't put expressions in the elements of a DO loop. Nobody could tell me why.

So I bought a book on compilers https://www.amazon.com/compiler-generator-William-M-McKeeman... and dove in. I ported got the XPL compiler to run on our SIGMA 5 and actually used it in some production jobs. Then, I got a job at Sycor on a team of 3 writing a compiler for a derivative of PL/M targeting the 8085. The compiler was written in Bliss 36. Was serious fun and had major impact on how they developed their software.

I have long left Fortran behind. I have many other languages under my belt now, and no desire to revisit.

Thanks! Especially thanks for mentioning: https://en.wikipedia.org/wiki/SDS_Sigma_series and Sycor. I didn't know about these up to now.

The paper by McGee and Schmidt (1985):

https://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/198600...

"Discovery of the Kalman Filter as a Practical Tool for Aerospace and Industry -- Leonard A. McGee and Stanley F. Schmidt"

Are they just talking about the extended kalman filter? If so it is funny that there was such a big conceptual gap between the linear and linearized versions (i.e. a few years gap). Hindsight is a wonderful thing.

Nope, as far as I can tell, the schmidt-kalman filter is a way of reducing dimensionality in a KF. You split the states between those you are interested in and those you aren't. Sometimes those states you don't care about (e.g. sensor biases) are still important for estimating those you do care about (e.g. position). Adding a state to a typical KF for each of these dimensions is one solution, but it's expensive (covariance calcs scale quadratically with dimension). The Schmidt-Kalman filter is another solution.

Reply on news.ycombinator.com