## Chapter 14. How Elegant Code Evolves with Hardware The Case of Gaussian
Elimination

*Jack Dongarra and Piotr Luszczek*

The increasing availability of
advanced-architecture computers, at affordable costs, has had a
significant effect on all spheres of scientific computation. In this chapter, we’ll show the
need for designers of computing algorithms to make expeditious and
substantial adaptations to algorithms, in reaction to architecture
changes, by closely examining one simple but important algorithm in
mathematical software: Gaussian elimination for the solution of linear
systems of equations.

At the application level, science has to be captured in mathematical models, which in turn are expressed
algorithmically and ultimately encoded as software. At the software level,
there is a continuous tension between performance and portability on the
one hand, and understandability of the underlying code. We’ll examine
these issues and look at trade-offs that have been made over time. Linear
algebra—in particular, the solution of linear systems of equations—lies at
the heart of most calculations in scientific computing. This chapter
focuses on some of the recent developments in linear algebra software
designed to exploit advanced-architecture computers over the
decades.

There are two broad classes of algorithms: those for dense matrices and those for sparse matrices. A matrix is called
*sparse* if it contains a substantial number of zero elements. For sparse matrices, radical savings in space ...