On Algorithmic Science and Engineering: An Emerging Core Discipline of ComputingMarch 24, 2006
Figure 1. A visual icon.
Algorithmic science is the theoretical and empirical study, and the practical implementation and application, of real-number algorithms, in particular for solving problems of continuous mathematics that arise in the fields of optimization and numerical analysis. This is not to exclude algorithms of discrete mathematics, which form a backbone for computer science but which, within this characterization, take second place to algorithms of continuous mathematics.
We attach to "algorithmic" the word "science" in its fullest sense. Thus, as with any scientific field, the discipline has three main forms of expression:
- Theoretical algorithmic science establishes the convergence, complexity, and numerical stability of algorithms and provides the foundations for underlying computational models.
- Experimental algorithmic science studies algorithms through the use of constructed models and explores algorithmic processes, from which computational metaphors are often derived, within physical, chemical, and biological systems in nature.
- Computational algorithmic science uses the computer and the large body of associated software tools, for example, Mathematica, MATLAB, as a laboratory for the study of algorithms. Also included are practical implementation and the development of reliable, robust mathematical software, i.e., the "technology" of the subject.
For additional background and discussion, see Nazareth .
In this essay, algorithmic science is considered in detail in the broader context of scientific, engineering, and mathematical computing. An emerging discipline---algorithmic science and engineering (AS&E)---is contrasted with the well-established, complementary discipline of computer science and engineering (CS&E).
A Visual Schema
To frame the discussion, we created the visual schema shown in Figure 1. In the figure, each labeled band is called an "arena."
Mathematics, the core arena of Figure 1, is commonly partitioned into the real number system and algebra, geometry, and analysis---with many additional subdivisions and areas of intersection; see, for instance, the definitive, three-volume survey . Within this integrated discipline, "pure" mathematics, the heart of mathematics, is symbolized by the inner perimeter of the mathematics arena; "applied" mathematics is symbolized by the outer perimeter, bordering science and engineering.
Surrounding mathematics is the arena of science,* often partitioned into the physical, chemical, and biological sciences. Further partitioning would identify the many specific sciences within each of these three broad subdivisions. "Mathematical science," interfacing with mathematics, can be viewed as occupying the inner perimeter of the science arena, and "applied science" the outer perimeter, at the interface with engineering. In our schema, "mathematical science" and "applied mathematics" are overlapping designations, the former reflecting the perspective of science and the latter the perspective of mathematics. The region in which applied mathematicians and physicists find common ground is called mathematical physics; ap-plied mathematicians and biologists intersect in the region called mathematical biology.
Engineering, the outermost arena of Figure 1, again has many subdivisions: mechanical, chemical, electrical, and so on. In this case the inner perimeter symbolizes the interface with science, specifically the subject known as "engineering science," with the outer perimeter representing "applied" engineering in its usual sense: the development of engineered objects premised on science and mathematics, e.g., bridges, aeroplanes, and computers. The diagonal lines at the corners of the science arena, by explicitly linking the other two arenas of Figure 1, serve as a reminder that engineering is also connected to mathematics. From the perspective of the engineer, the linking diagonals represent "mathematical engineering"; from the perspective of the mathematician, they represent the applicable region known as "engineering mathematics." We think that they also add an appealing visual dimension to the figure.
Some academic fields naturally traverse arena boundaries. Computer science, for instance, has its origins in theoretical models of computation and complexity developed by mathematicians, which lie at its foundation. But the field evolved subsequently, in tandem with the electronic computer, into a separate discipline that unites science and engineering. The field is now commonly designated computer science and engineering (CS&E) or electrical engineering and computer science (EE&CS). (This union arises because digital computers, both their hardware and their software components, are themselves engineered objects.) Similarly, statistics traverses the boundary between the mathematics and science arenas, uniting mathematical probability (measure) theory and the science of statistical data.
The three axes at the center of Figure 1 depict the three main modes, or forms of investigation, employed within every branch of mathematics, science, and engineering--namely, the theoretical, experimental, and computational modes. Notice that "theoretical" does not necessarily imply the use of mathematics. Much of evolutionary biological theory, for example, is non-mathematical. "Computational" is relevant across the board, even to computer science, i.e., the term "computational computer science" is not redundant. For example, properties of the hashed symbol tables that are widely used in computer software can be studied computationally, i.e., via simulation on a computer.
The central dot of the figure, from which the three axes emanate, can represent any subfield in any of the arenas. Evolutionary biology, for instance, can be investigated in theory, by experimentation in the laboratory, or via simulations on a computer. Within mathematics, cf. the recent, landmark monograph of Borwein and Bailey  on the experimental/computational mode.
In summary, the inner perimeter of each arena---mathematics, science, and engineering---represents the pure side of its associated subject, and the outer perimeter represents the applied. Mathematics "applied" borders science (and engineering) "pure"; science "applied" borders engineering "pure." And every subfield within the arenas, symbolized by the central dot, has three main modes corresponding to the three axes. Because the computer can be used as a "laboratory," the distinction between experimental and computational can become blurred. The term "empirical" could then designate the union of these two modes, the counterpart to "theoretical," and be symbolized by the plane defined by the two horizontal axes in Figure 1.
We designed Figure 1 to facilitate the discussion that follows. We call the schema an "icon" because it is akin more to a "compound symbol" for the complex interrelationships between mathematics, science, and engineering than to a strict pictorial representation of them.
Algorithmic Science & Engineering (AS&E)
Before turning to the position of algorithmic science in Figure 1, we consider its foundational areas of numerical analysis and optimization. As the name "numerical analysis" suggests, the field arose within mathematics as the region of analysis in which number representation and numerical processes play a central role, in particular analysis of the effects of rounding error. This aspect is exemplified by the classic monographs of Wilkinson [11,12]. Today, we interpret the subject far more broadly---as the study of numerical models and algorithms---and it has diffused widely into most branches of the natural sciences and engineering. For further background, see the panel discussion in Renegar, Shub, and Smale . The field of optimization, which came to flower in the classic monograph of Dantzig , has enjoyed a similar success. These works, , [11,12], all three of which appeared in 1963–65, are the crown jewels of optimization and numerical analysis, two interrelated fields that have advanced rapidly, in tandem with computer hardware developments, during the past five decades. Key facets of the two fields are:
- The art of modeling, i.e., casting real applications into one of a wide array of basic mathematical models. In the case of numerical analysis, these models generally take the form of linear or nonlinear equation-solving (including algebraic and differential equations), defined over finite- or infinite-dimensional spaces. In the case of optimization, they generally involve the maximization or minimization of objective functions over feasible regions defined by equality and/or inequality constraints, again in finite or infinite dimensions.
- The science of algorithmics, i.e., the invention and implementation of efficient algorithms for solving models.
- The mathematics of models and algorithms, in particular the analysis of solution sets and other properties of, and duality relationships between, various classes of models; and the analysis of algorithms from the standpoints of convergence, complexity, and numerical stability.
While the modeling aspects of optimization and numerical analysis are often best conducted within, or in close partnership with, the scientific or engineering areas in which the applications originate, each of these fields has retained a strong algorithmic core and an associated mathematics of models and algorithms for solving them. This retained area is frequently subsumed nowadays under the rubric of scientific computing. Here, "computing" broadly connotes algorithms and software, but the qualifying adjective "scientific" is ambiguous, used in two senses: "of, relating to, or exhibiting the methods or principles of science" and "as it applies to the sciences." The first interpretation, in conjunction with "computing" as "algorithmics," yields the term "scientific algorithmics," or "algorithmic science." The second, oft-used interpretation of "scientific" is regrettable here in that it embraces only the science arena of Figure 1. As a more appropriate name, we suggest "scientific, engineering, and mathematical computing," which explicitly embraces all three arenas. (We think that this alternative choice has an appealing abbreviation: sci-en-math computing.)
The name "algorithmic science" has the advantage of clearly identifying the objects---finitely terminating, teleological dynamical processes defined abstractly as mathematical objects, realized concretely in the form of computer software, or found empirically in nature---that lie at the heart of the discipline and are studied scientifically. As with any scientific discipline, the three modes---theory, experiment,† and computation---are readily evident, and the discipline interfaces with mathematics and engineering. From the viewpoint of science, the interface with mathematics would be in mathematical algorithmic science; from the viewpoint of mathematics, it would be the relevant part of algorithmic, or constructive, applied mathematics.
The intersection of algorithmic science with the arena of engineering involves the development, or engineering, of so-called mathematical software, an integral part of the subject. For this reason, and also for the purpose of emphasizing the importance of applications, we henceforth use the name "algorithmic science and engineering," or AS&E, for the emerging discipline. Those who prefer can substitute the more recognizable "scientific, engineering, and mathematical computing," with AS&E as its core area. (The word "algorithm" could well become part of everyday discourse in the future---see, for example, Berlinski .)
The study of real-number algorithms of continuous mathematics is central to AS&E, just as the corresponding study of algorithms of discrete mathematics---more specifically, "concrete" mathematics as defined in Graham, Knuth, and Patashnik ---is at the heart of computer science; see, in particular, the discussion in Knuth . It is around this central activity that AS&E can encompass a wide domain: grand challenges of computing (e.g., algorithmic investigations of protein folding or the intriguing near-optimality of the genetic code); new computing paradigms (e.g., the dramatic paradigm-shift proposed by Wolfram ); cross-fertilizations (e.g., the algebraic eigenproblem from the viewpoint of nonlinear optimization and equation-solving; foundations (e.g., the real-number computational models of Blum, Cucker, Shub, and Smale ); and so on. An emergent AS&E discipline within a university would help to integrate real-number algorithmic research, which is currently conducted in numerous scattered departments, with little intersection or communication. Its recognition would thus have significant benefits for research.
In addition, significant educational advantages would be gained from the recognition of AS&E within the formal structure of a university, as a counterpart of the now well-established discipline of computer science, or the related CS&E and EE&CS. Requirements for graduate qualifying examinations should then be set in a way that maintains an appropriate balance between mathematics and computer science. Coherent training could be provided for much-needed real-number computing professionals in academia and industry, producing graduating students who would be well positioned in the job market. Mathematical software engineering would be a respectable activity within AS&E and would be officially recognized and rewarded, as is the writing of (non-mathematical) software in computer science. Writing a large piece of software is as challenging as proving a convergence theorem; it is perhaps even harder---the computer is an unrelenting taskmaster---yet mathematical software development currently receives little reward in mathematics or mathematical sciences departments. An AS&E discipline could more comfortably embrace a spectrum of orientations, ranging from theorem provers to mathematical software developers, all under the unifying rubric of computing, algorithms, and software.
Just as computer science, or its embracing CS&E and EE&CS disciplines, became established at universities during the past four decades, we can hope to see AS&E, or an embracing scientific, engineering, and mathematical computing discipline, emerge in decades to come. In this regard, it is worth recalling Knuth's original vision of computing and computer science as the "study of algorithms" . This vision could be realized in a university by a full-fledged AS&E that works hand in hand with its counterpart CS&E, creating a situation whereby the study of algorithms for continuous and discrete mathematics would be emphasized more equally. Only time will tell whether a desirable integration of real-number algorithmic-oriented research and education will indeed become a reality, or whether fragmentation of the underlying fields of algorithmic numerical analysis and optimization will continue.
A blueprint for an informally structured, Internet-based algorithmic science and engineering research center can be found at http://www.math.wsu.edu/faculty/nazareth/aserc.pdf.
 D. Berlinski, The Advent of the Algorithm: The Idea that Rules the World, Harcourt, New York, 2000.
 H. Behnke et al., eds., Fundamentals of Mathematics. Volume I: Foundations of Mathematics/The Real Number System and Algebra. Volume II: Geometry. Volume III: Analysis, The MIT Press, Cambridge, MA (translated by S.H. Gould), 1974.
 L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation (with a foreword by R.M. Karp), Springer–Verlag, New York, 1998.
 J. Borwein and D. Bailey, Mathematics by Experiment: Plausible Reasoning in the 21st Century, A.K. Peters, Nantick, MA, 2004.
 G.B. Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, NJ, 1963.
 R. Graham, D.E. Knuth, and O. Patashnik, Concrete Mathematics: A Foun-dation for Computer Science, Addison–Wesley, Reading, MA, 1989.
 D.E. Knuth, Selected Papers on Computer Science, CSLI Lecture Notes No. 59, Cambridge University Press, Cambridge, England, 1996.
 J.L. Nazareth, Differentiable Optimization and Equation Solving: A Treatise on Algorithmic Science and the Karmarkar Revolution, Canadian Mathematical Society (CMS) Books in Mathematics Series, Springer–Verlag, New York, 2003.
 J. Renegar, M. Shub, and S. Smale, eds., Mathematics of Numerical Analysis, American Mathematical Society, Providence, RI, 1996.
 L.N. Trefethen, The definition of numerical analysis, SIAM News, 25 (1992), 6.
 J.H. Wilkinson, Rounding Errors in Algebraic Processes, Prentice–Hall, Englewood Cliffs, NJ, 1963.
 J.H. Wilkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, England, 1965.
 S. Wolfram, A New Kind of Science, Wolfram Media, Inc., Champaign, IL, 2002.
J.L. Nazareth (firstname.lastname@example.org) is a professor emeritus at Washington State University and an affiliate professor at the University of Washington.
*Here we consider only the so-called hard sciences, in particular the natural sciences.
†For example, the experimental study of algorithmic processes involving annealing, spin glasses, protein folding, or evolution based on genetic recombination and mutation.