Skip to content

Heinz Rutishauser

Abstract

Heinz Rutishauser (1918–1970) was a Swiss mathematician at ETH Zurich who showed in 1951 that a computer could translate algebraic formulas into its own instructions, one of the first descriptions of what is now called a compiler. He learned programming on Konrad Zuse’s rented Z4, helped plan the ERMETH, invented the qd algorithm and the LR transformation that led to the modern way of computing eigenvalues, and was one of the thirteen authors of ALGOL 60. Heart disease limited his last fifteen years; he died at his desk at 52.

Heinz Rutishauser
Heinz Rutishauser. Image: ETH Library, photographer unknown, CC BY-SA 4.0, via Wikimedia Commons.

Weinfelden to Trogen

Rutishauser was born on 30 January 1918 in Weinfelden in the canton of Thurgau, the son of the headmaster of the cantonal school in Frauenfeld. His father died in 1931 and his mother in 1934, and he, his younger brother, and his younger sister grew up in their uncle’s house. He passed his Matura in 1936 and studied mathematics at ETH Zurich, with interruptions for service in the fortress artillery in the Gotthard region, graduating in 1942. For three years he was assistant to Walter Saxer while writing a doctorate in complex function theory, awarded with distinction in 1948. In between he taught mathematics at the secondary schools in Glarisegg and Trogen.

America and the Z4

In 1948 the topologist Eduard Stiefel founded the Institute for Applied Mathematics at ETH and hired two assistants, Rutishauser and the electrical engineer Ambros Speiser. Stiefel wanted ETH to build its own computer, and he sent both men to the United States to see how it was done. They stayed from late 1948 until the end of 1949, mostly at Harvard with Howard Aiken and at the Institute for Advanced Study in Princeton with John von Neumann, and visited ENIAC at Aberdeen.

When they returned in December 1949 the plan had changed. In July 1949 Stiefel had signed a contract to rent Konrad Zuse’s relay computer Z4, and from August 1950 it ran at ETH. In Speiser’s words it “had 64 storage locations for floating-point numbers and performed 1,000 basic operations per hour”. It was slow, but it meant Zurich could test numerical methods on a real machine years before anyone else on the continent. Friedrich L. Bauer later reckoned that the Z4 gave Rutishauser a four-year lead in practical programming over his German colleagues. Its most famous job was a system of 106 linear equations for the Grande Dixence dam, for which Stiefel developed the conjugate gradient method (found independently by Magnus Hestenes).

Automatische Rechenplanfertigung

Programming the Z4 meant punching every operation onto tape by hand. Rutishauser asked whether the machine could do that work itself. In a lecture at the GaMM meeting in Freiburg at the end of March 1951, and in his habilitation thesis of the same year, he described how a program-controlled calculator could take an arithmetic formula, with parentheses and operator precedence, and generate the sequence of machine instructions that evaluates it. The method also handled loops over indexed quantities. It was published in 1952 as Automatische Rechenplanfertigung bei programmgesteuerten Rechenmaschinen (“automatic preparation of computing plans for program-controlled computers”), number 3 of the institute’s reports.

The key claim was that the same machine that runs a program can also write it. The Soviet computer scientist Andrei Ershov later called such a thing a “programming program”; today it is a compiler (see The Compiler). Rutishauser had no chance to run his translator on the Z4. His notation, called Superplan, used the German word für to introduce a loop over an index, the ancestor of the for keyword that ALGOL 58 and its descendants still use.

Bauer, who met Rutishauser in his office on 19 February 1952, called the 1951 work the start of his own path through academic life. Bauer and Klaus Samelson’s stack-based formula translation of 1955 to 1957 was, in Bauer’s words, “an essential improvement over the Rutishauser method of 1951, as it was much faster” (see Friedrich L. Bauer).

ERMETH

ERMETH
The ERMETH on museum display. Image: tomislav medak, CC BY 2.0, via Wikimedia Commons.

The machine Stiefel had sent his assistants to study was the ERMETH (Elektronische Rechenmaschine der ETH). Rutishauser and Speiser were Stiefel’s senior assistants on the project, with Speiser leading the engineering. Rutishauser’s share included the software, among it a run-time organisation for subroutine returns that handled them last-in, first-out. The machine had about 1,500 tubes, worked in decimal, and stored 10,000 words on a magnetic drum weighing 1.5 tonnes. Speiser left in 1955 to set up IBM’s research laboratory in Zurich, and others finished the job. ERMETH went into operation in 1956, about a year after the PERM in Munich, with about a hundred times the speed of the Z4. From 1958 a paper-tape reader let it run ALGOL programs. It was switched off in October 1963 and is now in the Museum of Communication in Bern.

ALGOL

In 1955 Rutishauser used a GaMM meeting to call for a common programming language. A working group from Zurich, Munich, and later Darmstadt and Mainz formed (the ZMD group), and Rutishauser organised its first large meeting, in Lugano in autumn 1957. That meeting decided to invite the ACM and the British Computer Society to a joint conference. The BCS did not reply; the ACM did, and from 27 May to 2 June 1958 eight people from both sides met at ETH Zurich and produced the International Algebraic Language, published in 1959 as ALGOL (see ALGOL and the ALGOL Family).

Rutishauser was also one of the thirteen at the Paris conference of 11 to 16 January 1960 that produced ALGOL 60. Bauer judged that his share was “more than a thirteenth”. In the 1960s he kept working in IFIP Working Group 2.1, though less actively; he disliked the direction that led to ALGOL 68. He wrote Description of ALGOL 60 (1967), volume I, part a of Springer’s Handbook for Automatic Computation, and spent much of his effort on publishing numerical algorithms as carefully specified ALGOL procedures. That style of published, tested numerical procedures fed into the EISPACK and LINPACK libraries.

qd and LR

Rutishauser’s best-known mathematical work grew out of the same habit of turning a method into a procedure that terminates. In 1954 he published the quotient-difference algorithm for finding the zeros of polynomials and the eigenvalues of matrices, and named it an “algorithm” at a time when applied mathematicians rarely used the word. Shortly afterwards he recognised that a step of the qd algorithm could be read as a factorisation of a tridiagonal matrix into a lower and an upper triangular part, multiplied back together in the opposite order. Generalised to full matrices, this became the LR transformation (1955 to 1958), the direct predecessor of the QR algorithm that John Francis and Vera Kublanovskaya published in 1961 and that most numerical software still uses for eigenvalues. Martin Gutknecht and Beresford Parlett reconstructed the path from qd to LR in 2011. In 1955 Rutishauser and Bauer found that they had independently arrived at the same quadratically convergent variant and published it jointly in the Comptes rendus of the Paris Academy.

Illness and Death

ETH made Rutishauser an associate professor (ausserordentlicher Professor) in 1955 and a full professor in 1962. In 1968 he became head of ETH’s new group for computer science, the forerunner of the department in which Niklaus Wirth later built Pascal.

His heart had troubled him since at least the night of 16 February 1955, which he spent ill in Bauer’s house in Munich; he recovered after a long stay in Klosters. He survived a heart attack in the autumn of 1964, avoided flying to the United States, and in the late 1960s turned down a chair at the Leibniz Computing Centre in Munich, which the university and the Bavarian Academy had offered him, because of his health. He became seriously ill in 1969 and died at his desk in Zurich of acute heart failure on 10 November 1970. Bauer dedicated his 1971 textbook Informatik to him. Rutishauser’s lectures on numerical mathematics appeared posthumously in 1976.

📚 Sources