A Mathematician Looks at the Collins English Dictionary

190324-1322-52_9515a.jpg

I have several dictionaries on my shelf, among which is a well-thumbed Collins English Dictionary (third edition, 1991). Earlier this year I acquired the thirteenth edition (2018). At 26.5cm high, 20cm wide, and 6.5cm deep, and weighing approximately 2.5kg, it’s an imposing tome. It’s printed on thin paper with minimal show-through and in a specially designed font (Collins Fedra) that is very legible.

The thirteenth edition, which I will abbreviate to CED13, is a wonderful acquisition for any dictionary lover. It has a wide coverage, including

  • new words such as micromort (“a unit of risk equal to a one-in-a million chance of dying”),
  • obscure words such as compotation (“the act of drinking together in a company”), and
  • a wide selection of proper nouns, including my home town Eccles and, somewhat unexpectedly, Laurel and Hardy and Torvill and Dean (Olympic ice dance champions, 1984).

It has no appendices on English usage, mathematical symbols, chemical elements, etc., as are found in many dictionaries—which is fine with me as I rarely use them.

I decided to take a close look at some of the mathematical words in the CED.

determinant n maths: a square array of elements that represents the sum of certain products of these elements, used to solve simultaneous equations, in vector studies, etc.”

This definition has two problems. First, a determinant is the sum, not something that represents the sum. Of, course, one will find in some textbooks statements such as “swapping two rows of a determinant changes its sign”, but it’s odd that this informal usage of determinant as array is the only one mentioned. A second problem is that the determinant is not a sum of products: it is a signed sum of products and it is the permanent (not in this dictionary) that is obtained by taking all positive signs.

matrix n maths a rectangular array of elements set out in rows and columns, used to facilitate the solution of problems, such as transformation of coordinates.”

A matrix is more than just an array: its key characteristic is that it has algebraic operations defined on it.

rounding: n computing a process in which a number is approximated as the closest number that can be expressed using the number of bits or digits available.”

Rounding is not specifically a computing term—it’s more fundamentally a mathematical operation and predates computing. Bits are special cases of digits. And rounding does not have to be to the closest number: in some situations once needs to round to the next larger or smaller number.

index n maths c a subscript or superscript to the right of a variable to express a set of variables, as in using x_i for x_1, x_2, x_3, etc”

An index does not (except maybe in informal usage) express a set, but rather identifies a member of a set.

supercomputer n a powerful computer that can process large quantities of data of a similar type very quickly.”

Supercomputers do mathematical calculations (and are ranked on their speed in doing so), which is not apparent from this definition. I’m also not sure why “of a similar type” is necessary. The PC on which I am typing is a supercomputer according to this definition!

integral n maths the limit of an increasingly large number of increasingly smaller quantities, related to the function that is being integrated (the integrand). The independent variables may be confined within certain limits (definite integral) or in the absence of limits (indefinite integral).”

This seems to be an attempt to state informally the Riemann sum definition of definite integration. Sadly, it’s technically incomplete and sure to baffle anyone who doesn’t already know about Riemann sums. It would have been much better to simply say that integration is the inverse of differentiation. The second sentence is grammatically incorrect.

fractal maths n a figure or surface generated by successive subdivisions of a simpler polygon or polyhedron, according to some iterative process.”

Surely any definition should mention fractional dimension and self-similarity? This definition excludes the fractal that is the boundary of the Mandelbrot set.

I’m not too surprised by these weaknesses, because in 1994 I wrote an article Which Dictionary for the Mathematical Scientist? (PDF file here) in which I evaluated several dictionaries (including CED3) from the point of view of their mathematical words and found problems such as those above in several of them.

Despite these criticisms, I very much like this dictionary and I use it as much as the other dictionaries on my desk. It is especially good on the computing side. I was pleased to see that my favourite editor, emacs, is included (though I’m not sure why it is not capitalized). Vi users will be sad to hear that Vi is not included. A good number of programming languages are present, including awk (uncapitalized), Java, and Javascript, but not, C++ (how would that be alphabetized?), Python, or R.

A particularly notable definition is

flops or FLOPS n acronym for floating-point operations per second: used as a measure of computer processing power (in combination with a prefix): megaflops; gigaflops.

This is much better than the Oxford English Dictionary’s definition of the singular flop as “a floating-point operation per second”. There are also entries for petaflop,10^{15} floating-point operations a second”, and teraflop, “a thousand billion floating-point operations a second”. I just wish the latter definition contained “10^{12}“, because there is scope for misunderstanding because of the alternative meaning of a billion as a million million in the UK.

Posted in books | Tagged | 1 Comment

Better LaTeX Tables with Booktabs

One of the joys of \LaTeX is that it makes it so easy to typeset tables. I’ve created many \LaTeX tables and I’ve always taken care to fine-tune them, most often by inserting commands of the form \rule{0cm}{8pt} to stop superscripts hitting a horizontal rule in the line above.

I’ve been aware for a while of a \LaTeX package called booktabs that claims to produce more beautiful tables that more closely resemble those used in traditional typesetting. I was dissuaded from trying it by three things: the results looked rather spread out, the package discourages the use of vertical rules (which I thought I needed), and I wasn’t sure if publishers such as SIAM would allow it to be used in their journals.

I was encouraged to give booktabs a try while I was preparing the third edition of Handbook of Writing for the Mathematical Sciences. I redid the tables from the previous edition using the package and, after some experimentation, became convinced that booktabs is indeed a great aid to producing better tables.

The best way to illustrate the attractions of booktabs is with a simple example. This table is from a 2017 SIAM J. Sci. Comput. paper of which I am a co-author: table_ex1.jpg

The original table did not have the vertical rules at the sides or the horizontal rule at the bottom, but I have added them since many people include them.

Here is a revised version of the table created with booktabs:

table_ex2.jpg

The second table dispenses with all the vertical rules and adds two partial horizontal rules to demarcate the span of the pairs of columns covered by the two tol values. Notice the thicker rules at the top and bottom and the greater spacing between lines. The booktabs version of the table is more aesthetically pleasing. It is also slightly easier to typeset. The rules at the top, middle, and bottom are typed with \toprule, \midrule, and \botomrule. The subrules are typed with \cmidrule{m-n} to span columns m to n. The usage \cmidrule(lr){m-n} crops (on the left and right) the rules so that adjacent subrules do not merge.

Here is the source code for the two tables:

% First version of table.
\begin{tabular}{|l|c|c|c|c|c|l|}\hline
& \multicolumn{3}{c|}{$\tol=\tols$} & \multicolumn{3}{c|}{$\tol=\told$}\\
           & $mv$  & Rel.~err & Time    & $mv$  & Rel.~err & Time   \\\hline
\trigmv    & 11034 & 1.3e-7 & 3.9 & 15846 & 2.7e-11 & 5.6 \\
\trigexpmv & 21952 & 1.3e-7 & 6.2 & 31516 & 2.7e-11 & 8.8 \\
\trigblock & 15883 & 5.2e-8 & 7.1 & 32023 & 1.1e-11 & 1.4e1\\
\expleja   & 11180 & 8.0e-9 & 4.3 & 17348 & 1.5e-11 & 6.6 \\\hline
\end{tabular}

% Second version of table, with booktabs.
\begin{tabular}{lcccccl}\toprule
& \multicolumn{3}{c}{$\tol=\tols$} & \multicolumn{3}{c}{$\tol=\told$}
\\\cmidrule(lr){2-4}\cmidrule(lr){5-7}
           & $mv$  & Rel.~err & Time    & $mv$  & Rel.~err & Time\\\midrule
\trigmv    & 11034 & 1.3e-7 & 3.9 & 15846 & 2.7e-11 & 5.6 \\
\trigexpmv & 21952 & 1.3e-7 & 6.2 & 31516 & 2.7e-11 & 8.8 \\
\trigblock & 15883 & 5.2e-8 & 7.1 & 32023 & 1.1e-11 & 1.4e1\\
\expleja   & 11180 & 8.0e-9 & 4.3 & 17348 & 1.5e-11 & 6.6 \\\bottomrule
\end{tabular}

Despite my initial skepticism, it does seem possible to manage without vertical rules in tables. Indeed, the Chicago Manual of Style (17th edition, 2017) advises that “Vertical rules should be used sparingly—for example, when a table is doubled up … or as an aid to comprehension in an especially long or complex table”. The extra space that booktabs puts around horizontal rules makes the table nicer to look at and helps to avoid the problem of superscripts hitting the rule above. And, importantly, SIAM are happy to for authors to use booktabs in their papers.

I am now using booktabs in all my \LaTeX code.

For more before-and-after examples of tables, which illustrate table design as well as the use of booktabs, see Handbook of Writing for the Mathematical Sciences (third edition, 2020).

One booktab tip that I needed in producing the Handbook was to reduce the space at the edges of some of the widest tables by shortening the horizontal rules. This can be done by putting @{} at the beginning and end of the column formatting argument. For the example above, this is done with

\begin{tabular}{@{}lcccccl@{}}\toprule

This blog contains various other posts about \LaTeX.

Posted in LaTeX | 2 Comments

What’s New in MATLAB R2019a and R2019b?

I didn’t have time earlier this year to write about the first MATLAB release of 2019, so in this post I will discuss R2019a and R2019b together. As usual in this series, I concentrate on the features most relevant to my work.

Modified Akima Cubic Hermite Interpolation (R2019b)

makima_example.jpg

A new function makima computes a piecewise cubic interpolant with continuous first-order derivatives. It produces fewer undulations than the existing spline function, with less flattening than pchip. This form of interpolant has been an option in interp1, interp2, interp3, interpn, and griddedInterpolant since R2017b and is now also a standalone function. For more details see Cleve Moler’s blog post about makima, from which the code used to generate the image above is taken.

Linear Assignment Problem and Equilibration (R2019a)

The matchpairs function solves the linear assignment problem, which requires each row of a matrix to be assigned to a column in such a way that the total cost of the assignments (given by the “sum of assigned elements” of the matrix) is minimized (or maximized). This problem can also be described as finding a minimum-weight matching in a weighted bipartite graph. The problem arises in sparse matrix computations.

The equilibrate function take as input a matrix A (dense or sparse) and returns a permutation matrix P and nonsingular diagonal matrices R and C such that R*P*A*C has diagonal entries of magnitude 1 and off-diagonal entries of magnitude at most 1. The outputs P, R, and C are sparse. This matrix equilibration can improve conditioning and can be a useful preprocessing step both in computing incomplete LU preconditioners and in iterative solvers. See, for example, the recent paper Max-Balanced Hungarian Scalings by Hook, Pestana, Tisseur, and Hogg.

The scaling produced by equilibrate is known as Hungarian scaling, and its computation involves solving a linear assignment problem.

Function Argument Validation (R2019b)

A powerful new feature allows a function to check that its input arguments have the desired class, size, and other aspects. Previously, this could be done by calling the function validateattributes with each argument in turn or by using the inputParser object (see Loren Shure’s comparison of the different approaches).

The new feature provides a more structured way of achieving the same effect. It also allows default values for arguments to be specified. Function argument validation contains many aspects and has a long help page. We just illustrate it with a simple example that should be self-explanatory.

function fav_example(a,b,f,t)
  arguments
    a (1,1) double               % Double scalar.
    b {mustBeNumeric,mustBeReal} % Numeric type and real.
    f double {mustBeMember(f,[-1,0,1])} = 0 % -1, 0 (default), or 1.
    t string = "-"               % String, with default value.
  end
  % Body of function.
end

The functions mustBeNumeric and mustBeMember are just two of a long list of validation functions. Here is an example call:

>> a = 0; b = 2; f = 11; fav_example(a,b,f)
Error using fav_example
Invalid input argument at position 3. Value must be a member of ...
this set:
    -1
    0
    1 

One caveat is that a specification within the arguments block

v (1,:) double    

allows not just 1-by-n vectors (for any n) but also n-by-1 vectors, because of the convention that in many situations MATLAB does not distinguish between row and column vectors.

For more extensive examples, see New with R2019b – Function Argument Validation and Spider Plots and More Argument Validation by Jiro Doke at MathWorks Blogs.

Dot Indexing (R2019b)

One can now dot index the result of a function call. For example, consider

>> optimset('Display','iter').Display
ans =
    'iter'

The output of the dot call can even be indexed:

>> optimset('OutputFcn',{@outfun1,@outfun2}).OutputFcn{2}
ans =
  function_handle with value:
    @outfun2

Of course, these are contrived examples, but in real codes such indexing can be useful. This syntax was not allowed in R2019a and earlier.

Hexadecimal and Binary Values (R2019b)

One can now specify hexadecimal and binary values using the prefixes 0x or 0X for hexadecimal (with upper or lower case for A to F) and 0b or 0B for binary. By default the results have integer type.

>> 0xA
ans =
  uint8
   10
>> 0b101
ans =
  uint8
   5

Changes to Function Precedence Order (R2019b)

The Release Notes say “Starting in R2019b, MATLAB changes the rules for name resolution, impacting the precedence order of variables, nested functions, local functions, and external functions. The new rules simplify and standardize name resolution”. A number of examples are given where the meaning of code is different in R2019b, and they could cause an error to be generated for codes that ran without error in earlier versions. As far as I can see, though, these changes are not likely to affect well-written MATLAB code.

Program File Size (R2019b)

Program files larger than “approximately 128 MB” will no longer open or run. This is an interesting change because I cannot imagine writing an M-file of that size. Good programming practice dictates splitting a code into separate functions and not including all of them in one program file. Presumably, some MATLAB users have produced such long files—perhaps automatically generated.

For a modern introduction and reference to MATLAB, see MATLAB Guide (third edition, 2017)

mg3-front-cover.jpg
Posted in software | Tagged | 1 Comment

Happy 80th Birthday Cleve!

190529-1704-07_5195_0028.jpg

Today is the 80th birthday of Cleve Moler. Most readers will know Cleve as the inventor of MATLAB. MATLAB was originally a Fortran program that Cleve wrote to give students easier access to the EISPACK and LINPACK libraries. Cleve and John Little later founded The MathWorks and turned MATLAB into a commercial product.

190529-1708-22_5202_0034a.jpg

Cleve was a speaker at the conference Advances in Numerical Linear Algebra: Celebrating the Centenary of the Birth of James H. Wilkinson held in Manchester last May. We took the opportunity there to celebrate Cleve’s birthday in advance. A video of Cleve’s talk is included below.

Most recently I saw Cleve at the International Congress on Industrial and Applied Mathematics (ICIAM) conference in Valencia, where he spoke in the minisymposium Bohemian Matrices and Applications that I organized with Rob Corless. See Cleve’s blog post about his talk.

Happy birthday, Cleve!

(Photo credits: Gian Maria Negri Porzio.)

190529-1703-55_5194_0027.jpg

190529-1707-01_5198_0031.jpg

Four past SIAM presidents in Manchester, May 2019: Cleve Moler, Margaret Wright, Nick Trefethen and Nick Higham.

Posted in people | 1 Comment

The Argonne Tapes

A few weeks ago, I was in contact with Chris Paige, an emeritus Professor of Computer Science at McGill University, Montreal. I mentioned that Sven Hammarling and I are collecting information and memorabilia about the numerical analyst James Hardy Wilkinson FRS (1919-1986) for our Wilkinson webpage, and asked Chris if he knew of anything we didn’t already have. He replied “I have 5 1973 Video cassettes, each about 1 hour, by Jim labelled `Eigensystem Workshop June 1973′. … His wonderful lecturing style, and his idiosynchrasies, might be of interest, as well as the marvellous content.”

190328-1832-23_0001.jpg

The tapes contain four talks by Wilkinson and one by Cleve Moler from an Eigensystem Workshop held at Argonne National Laboratory, Illinois, USA, in June 1973.

The tapes are Scotch UC60 High Energy color Videocassettes, in U-matic format, one of which is shown to the right. Chris was able to have the tapes digitized and the results are pretty good given the age of the tapes. We have put the videos on the Numerical Linear Algebra Group YouTube channel and link to them below.

The videos were announced at the recent conference Advances in Numerical Linear Algebra: Celebrating the Centenary of the Birth of James H. Wilkinson, held in Manchester May 29-30, 2019.

  • Inverse Iteration – James H. Wilkinson, Eigensystem Workshop, Argonne National Laboratory, Argonne, Illinois, USA, June 1973.
Posted in people | Tagged , | Leave a comment

Numerical Algorithms for High-Performance Computational Science: Highlights of the Meeting

wordle_nahpcs.png
Word cloud from abstracts.

The Royal Society discussion meeting Numerical Algorithms for High-Performance Computational Science, which I organized with Jack Dongarra and Laura Grigori, was held in London, April 8-9, 2019. The meeting had 16 invited speakers and 23 contributed posters, with a poster blitz preceding the lively poster session.

The meeting brought together around 150 people who develop and implement numerical algorithms and software libraries—numerical analysts, computer scientists, and high-performance computing researchers—with those who use them in some of today’s most challenging applications. The aim was to discuss the challenges brought about by evolving computer architectures and the characteristics and requirements of applications, both to produce greater awareness of algorithms that are currently available or under development and to steer research on future algorithms.

Several key themes emerged across multiple talks, all in the context of today’s high performance computing landscape in which processor clock speeds have stagnated (with the end of Moore’s law) and exascale machine are just two or three years away.

  • An important way of accelerating computations is through the use of low precision floating-point arithmetic—in particular by exploiting a hierarchy of precisions.
  • We must exploit low rank matrix structure where it exists, for example in hierarchical (H-matrix) form, combining it with randomized approximations.
  • Minimizing data movement (communication) is crucial, because of its increasing costs relative to the costs of floating-point arithmetic.
  • Co-design (the collaborative and concurrent development of hardware, software, and numerical algorithms, with knowledge of applications) is increasingly important for numerical computing.

Applications treated included deep learning, climate modeling, computational biology, and the Square Kilometre Array (SKA) radio telescope project. We learned that the latter project needs faster FFTs in order to deal with the petabytes of data it will generate each year.

Papers from the meeting will be published in a future issue of Philosophical Transactions of the Royal Society A.

Here are the talks (in order of presentation), with links to the slides.

For a brief summary of the talks see George Constantinides’s insightful thoughts on the meeting.

Here are some photos from the meeting.

Posted in conferences | 1 Comment

Advances in Numerical Linear Algebra Conference and James Hardy Wilkinson Centenary

Wilkinson_021.jpg

This year marks the 100th anniversary of the birth of James Hardy Wilkinson, FRS. Wilkinson developed the theory and practice of backward error analysis for floating-point computation, and developed, analyzed, and implemented in software many algorithms in numerical linear algebra. While much has changed since his untimely passing in 1986, we still rely on the analytic and algorithmic foundations laid by Wilkinson.

This micro website about Wilkinson, set up by Sven Hammarling and me, contains links to all kinds of information about Wilkinson, including audio and video recordings of him.

With Sven Hammarling and Françoise Tisseur, I am organizing a conference Advances in Numerical Linear Algebra: Celebrating the Centenary of the Birth of James H. Wilkinson at the University of Manchester, May 29-30, 2019. Among the 13 invited speakers are several who knew or worked with Wilkinson. As well as focusing on recent developments and future challenges for numerical linear algebra, the talks will include reminiscences about Wilkinson and discuss his legacy.

Contributed talks and posters are welcome (deadline April 1, 2019) and some funding is available to support the attendance of early career researchers and PhD students.

Posted in conferences | Tagged | Leave a comment

Who Invented the Matrix Condition Number?

matlab_cond.jpg

The condition number of a matrix is a well known measure of ill conditioning that has been in use for many years. For an n\times n matrix A it is \kappa(A) = \|A\| \|A^{-1}\|, where \|\cdot\| is any matrix norm. If A is singular we usually regard the condition number as infinite.

The first occurrences of the term “condition number” and of the formula \kappa(A) = \|A\| \|A^{-1}\| that I am aware of are in Turing’s 1948 paper Rounding-Off Errors in Matrix Processes. He defines the M-condition number n\|A\|_M \|A^{-1}\|_M and the N-condition number n^{-1}\|A\|_F \|A^{-1}\|_F, where \|A\|_M = \max_{i,j}|a_{ij}| and \|A\|_N = (\sum_{i,j}|a_{ij}|^2)^{1/2}, the latter N-norm being what we now call the Frobenius norm. He suggests using these condition numbers to measure the ill conditioning of a matrix with respect to linear systems, using a statistical argument to make the connection. He also notes that “the best conditioned matrices are the orthogonal ones”.

In his 1963 book Rounding Errors in Algebraic Processes, Wilkinson credits the first use of “condition number” to Turing and notes that “the term `ill-condition’ had been in common use among numerical analysts for some considerable time before this”. An early mention of linear equations being ill conditioned is in the 1933 paper An Electrical Calculating Machine by Mallock. According to Croarken, Mallock’s machine “could not adequately deal with ill conditioned equations, letting out a very sharp whistle when equilibrium could not be reached”.

As noted by Todd (The Condition of a Certain Matrix, 1950), von Neumann and Goldstine (in their monumental 1947 paper Numerical Inverting of Matrices of High Order) and Wittmeyer (1936) used the ratio of largest to smallest eigenvalue of a positive definite matrix in their analyses, which amounts to the 2-norm condition number \kappa_2(A) = \|A\|_2 \|A^{-1}\|_2, though this formula is not used by these authors. Todd called this the P condition number. None of the M, N or P names have stuck.

Nowadays we know that \kappa(A) can be thought of both as a measure of the sensitivity of the solution of a linear system to perturbations in the data and as a measure of the sensitivity of the matrix inverse to perturbations in the matrix (see, for example, Condition Numbers and Their Condition Numbers by D. J. Higham). How to formulate the definition of condition number for a wide class of problems was worked out by John Rice in his 1966 paper A Theory of Condition.

Posted in matrix computations | Leave a comment

Reflections on a SIAM Presidency

180325-2158-00_5921.jpg

The Drexel Dragon, on the Drexel University campus a couple of blocks from SIAM.

180325-2151-31_5912.jpg

Face Fragment (1975) sculpture, a block from SIAM.

My two-year term as SIAM President ended on December 31, 2018. It’s been an exciting and enjoyable two years, not least because of the excellent SIAM staff, leadership and other volunteers I’ve worked with.

My blog post Taking Up the SIAM Presidency and my SIAM News article Evolving and Innovating set out some ideas that I wanted to pursue during my two years as president. I will not attempt to review these here, but just list five highlights from the last two years.

  • We held the SIAM ADVANCE in April 2018: a two-day strategic planning workshop attended by 25 officers, staff, and other members of the SIAM community. The many ideas that emerged from the event are summarized in an 80-page report provided to the SIAM Council and Board of Trustees. Many of these have already been acted upon, others are in progress, and yet more will be considered in the future. My SIAM News article Advancing SIAM gives more details of the workshop.
  • A new journal SIAM Journal on Mathematics of Data Science was created. The first issue will be published in the first few months of 2019.
  • A new SIAM book series Data Science was created.
  • A new SIAG, the SIAM Activity Group on Applied and Computational Discrete Algorithms was approved and will begin operation in 2019.
  • The new SIAM website was launched (in June 2018).

180325-2148-44_5906.jpg

The location of the SIAM office: 3600 Market Street, Philadelphia.

Here is a summary of my presidency in numbers:

  • 12 trips to the USA (with 0 upgrades from economy class to business class).
  • 8 visits to SIAM headquarters and 1 SIAM staff meeting attended.
  • 20 “From the SIAM President” columns written for SIAM News: they are listed here.
  • 2 SIAM Council Meetings chaired and 4 SIAM Board meetings attended.
  • 1 ICIAM board meeting attended and 1 ICIAM board meeting and workshop hosted by SIAM in Philadelphia.
  • 2 meetings of the Joint Policy Board for Mathematics in Washington chaired and 2 attended.
  • Over 230 appointments made to committees and of candidates for elections (with the advice of various SIAM committees).
Posted in miscellaneous | Tagged | Leave a comment

Top Ten Posts of 2018

top10.jpg

According to the WordPress statistics, this blog received over 42,000 visitors and 73,000 views in 2018. These are the ten most-viewed posts published during the year.

  1. How to Program log z
  2. Tricks and Tips in Numerical Computing
  3. Conversations with Gil Strang
  4. What’s New in MATLAB R2018a?
  5. Numerical Linear Algebra Group 2017
  6. Bohemian Matrices in Manchester
  7. Half Precision Arithmetic: fp16 Versus bfloat16
  8. Palomino Blackwing Pencil Tribute to Ada Lovelace
  9. Joan E. Walsh (1932–2017)
  10. Lectures on Multiprecision Algorithms in Kácov

In addition, the article Differentiation With(out) a Difference in my SIAM News “From the SIAM President” column was the most viewed SIAM News article of 2018.

Posted in miscellaneous | 2 Comments