## The Strange Case of the Determinant of a Matrix of 1s and -1s

By Nick Higham and Alan Edelman (MIT)

In a 2005 talk the second author noted that the MATLAB det function returns an odd integer for a certain 27-by-27 matrix composed of $1$s and $-1$s:

>> A = edelman; % Set up the matrix.
>> format long g, format compact, det(A)
ans =
839466457497601


However, the determinant is, from its definition, a sum of an even number (27 factorial) of odd numbers, so is even. Indeed the correct determinant is 839466457497600.

At first sight, this example is rather troubling, since while MATLAB returns an integer, as expected, it is out by $1$. The determinant is computed as the product of the diagonal entries of the $U$ factor in the LU factorization with partial pivoting of $A$, and these entries are not all integers. Standard rounding error analysis shows that the relative error from forming that product is bounded by $nu/(1-nu)$, with $n=27$, where $u \approx 1.1 \times 10^{-16}$ is the unit roundoff, and this is comfortably larger than the actual relative error (which also includes the errors in computing $U$) of $6 \times 10^{-16}$. Therefore the computed determinant is well within the bounds of roundoff, and if the exact result had not been an integer the incorrect last decimal digit would hardly merit discussion.

However, this matrix has more up its sleeve. Let us compute the determinant using a different implementation of Gaussian elimination with partial pivoting, namely the function gep from the Matrix Computation Toolbox:

>> [Lp,Up,Pp] = gep(A,'p'); det(Pp)*det(Up)
ans =
839466457497600


Now we get the correct answer! To see what is happening, we can directly form the products of the diagonal elements of the $U$ factors:

>> [L,U,P] = lu(A);
>> d = diag(U); dp = diag(Up);
>> rel_diff_U_diags = norm((dp - d)./d,inf)
rel_diff_U_diags =
7.37206353875273e-16
>> [prod(d), prod(dp)]
ans =
-839466457497601          -839466457497600
>> [prod(d(end:-1:1)), prod(dp(end:-1:1))]
ans =
-839466457497600          -839466457497600


We see that even though the diagonals of the two $U$ factors differ by a small multiple of the unit roundoff, the computed products differ in the last decimal digit. If the product of the diagonal elements of $U$ is accumulated in the reverse order then the exact answer is obtained in both cases. Once again, while this behaviour might seem surprising, it is within the error bounds of a rounding error analysis.

The moral of this example is that we should not be misled by the integer nature of a result; in floating-point arithmetic it is relative error that should be judged.

Finally, we note that numerical evaluation of the determinant offers other types of interesting behaviour. Consider the Frank matrix: a matrix of integers that has determinant 1. What goes wrong here in the step from dimension 24 to 25?

>> A = gallery('frank',24); det(A)
ans =
0.999999999999996
>> A = gallery('frank',25); det(A)
ans =
143507521.082525


The Edelman matrix is available in the MATLAB function available in this gist, which is embedded below. A Julia notebook exploring the Edelman matrix is available here.

Posted in research | Tagged , | 2 Comments

## Fun Books for Learning Programming

I learned Fortran from the TV course and book by Jeff Rohl. Some years later I came across A FORTRAN Coloring Book by Roger Emanuel Kaufman (MIT Press, 1978). The text is entirely handwritten (even the copyright page), is illustrated with numerous cartoons, and is full of witty wordplay. Yet it imparts the basics of Fortran very well and I could have happily learned Fortran from it. It even describes some simple numerical methods, such as the bisection method. The book is one continuous text, with no chapters or sections, but it has a good index. I’ve long been a fan of the book and Des Higham, and I include three quotes from it in MATLAB Guide.

Kaufman’s book has attracted attention in cultural studies. In the article Bend Sinister: Monstrosity and Normative Effect in Computational Practice, Simon Yuill describes it as “the first published computing text to use cartoon and comic strip drawings as a pedagogic medium” and goes on to say “and it could be argued, is the archetype to the entire For Dummies series and all its numerous imitators”. I would add that the use of cartoons within magazine articles on computing was prevalent in the 1970s, notably in Creative Computing magazine, though I don’t recall anything comparable with Kaufman’s book.

A page from Illustrating C.

A book in a similar vein and from the same era, is the handwritten Illustrating Basic by Donald Alcock (Cambridge University Press, 1977). It’s a bit like Kaufman without the jokes, and is organized into sections. This was the first in a series of such books, culminating in Illustrating C (1992). Like Kaufman’s book, Alcock’s contain nontrivial examples and are a good way for anyone to learn a programming language.

Thinking Forth by Leo Brodie, about the Forth language, is typeset but contains lots of cartoons and hand-drawn figures. It was originally published in 1984 and is now freely available under a Creative Commons license.

A more recent book with a similarly fun treatment is Land of Lisp by Conrad Barski (No Starch Press, 2011). It teaches Common Lisp, coding various games along the way. It’s typeset but is heavily illustrated with cartoons and finishes with a comic strip.

## Org Mode Syntax Cheat Sheet

I’m a keen user of Emacs and Org mode for a variety of tasks, including

• note taking,
• generating documents for exporting to LaTeX, Word, or html.
• creating blog posts (notably for this blog, using Org2blog).

Although Org mode is usually associated with Emacs, it is a markup language in its own right, and one that is far more powerful and more standardized than the Markdown language.

I recently came across the excellent blog post Org-Mode Is One of the Most Reasonable Markup Language to Use for Text by Org enthusiast Karl Voit. In the post he includes a simple example displaying some of the most important aspects of Org syntax. I was struck by how much information can be conveyed in a short piece of Org code. I have adapted Karl’s example into this longer version:

#+TITLE: Org Mode Syntax Cheat Sheet
#+OPTIONS: toc:nil

# A comment line.  This line will not be exported.

Paragraphs are separated by at least one empty line.

*bold* /italic/ _underlined_ +strikethrough+ =monospaced=

https://nickhigham.wordpress.com/ A link without a description.

A DOI (digital object identifier) link:
[[doi:10.1093/comnet/cnv016][Matching Exponential-Based and Resolvent-Based Centrality Measures]]

A horizontal line, fill-width across the page:
-----

- First item in a list.
- Second item.
- Sub-item
1. Numbered item.
2. Another item.
- [ ] Item yet to be done.
- [X] Item that has been done.

LaTeX macros can be included: $x_2 = \alpha + \beta^2 - \gamma$.

**** TODO A todo item.
**** DONE A todo item that has been done.

#+BEGIN_QUOTE
This text will be indented on both the left margin and the right margin.
#+END_QUOTE

: Text to be displayed verbatim (as-is), without markup
: (*bold* does not change font), e.g., for source code.
: Line breaks are respected.

Some MATLAB source code:
#+BEGIN_SRC matlab
>> rand(1,3)
ans =
5.5856e-01   7.5663e-01   9.9548e-01
#+END_SRC

Some arbitrary text to be typeset verbatim in monospace font:
#+BEGIN_SRC text
Apples, oranges,
cucumbers, tomatoes
#+END_SRC

# calculated by hitting C-c C-c in Emacs on the #+TBLFM line.

|----------------+-----------+-----------+-------|
|----------------+-----------+-----------+-------|
| United States  |         7 |       497 |  71.0 |
| Unknown        |         4 |        83 |  20.8 |
| United Kingdom |         3 |        41 |  13.7 |
| Germany        |         3 |        29 |   9.7 |
| Netherlands    |         2 |        21 |  10.5 |
| Japan          |         1 |        18 |  18.0 |
|----------------+-----------+-----------+-------|
end


## Speed

Algorithm Trad does $O(n^3)$ flops at single precision and $O(n^2)$ flops at double precision. Algorithm New, however, does $O(n^3)$ flops at half precision and $O(n^2)$ flops at single and double precision. Both these statements assume, of course, that iterative refinement converges in a small number of iterations. There is therefore a potential two times speedup of Algorithm New over Algorithm Trad, since half precision runs at twice the speed of single precision on (for example) NVIDIA GPUs and AMD GPUs.

## Accuracy

Algorithm Trad converges as long as $\kappa_{\infty}(A) \le 10^8$ and it yields a forward error (defined by $\|x-\widehat{x}\|_{\infty}/\|x\|_{\infty}$, where $\widehat{x}$ is the computed solution) and a backward error both of order $10^{-8}$ (as shown by standard analysis). Our new rounding error analysis shows that Algorithm New has the same error bounds, but has the more stringent requirement $\kappa_{\infty}(A) \le 10^4$ for convergence.

## GMRES-IR

Now we replace the solve step in the loop of Algorithm New by an application of GMRES to the preconditioned system

$\widetilde{A} d_i \equiv \widehat{U}^{-1}\widehat{L}^{-1}Ad_i = \widehat{U}^{-1}\widehat{L}^{-1}r_i,$

where matrix–vector products with $\widetilde{A}$ are done at double precision and all other computations are done at single precision. Algorithm New now converges as long as $\kappa_{\infty}(A) \le 10^8$ and it yields forward and backward errors of order $10^{-8}$. In other words, it has the same numerical properties as Algorithm Trad but potentially does half the work (depending on the number of GMRES iterations needed to converge).

## Other Choices of Precision

Let H, S, D, and Q denote half precision, single precision, double precision, and quadruple precision, respectively. Algorithm New can be described as “HSD”, where the three letters indicate the precision of the factorization, the working precision, and the precision with which residuals are computed, respectively. Various combinations of letters produce feasible algorithms (20 in all, if we include fixed precision refinement algorithms, such as “SSS”), of which HSD, HSQ, HDQ and SDQ use three different precisions. Similar results to those above apply to the latter three combinations.

## Outlook

Our MATLAB experiments confirm the predictions of the error analysis regarding the behavior of Algorithm New and its GMRES-IR variant. They also show that the number of GMRES iterations in GMRES-IR can indeed be small.

Iterative refinement in three precisions therefore offers great promise for speeding up the solution of $Ax = b$. Instead of solving the system by an LU factorization at the working precision, we can factorize $A$ at half the working precision and apply iterative refinement in three precisions, thereby obtaining a more accurate solution at potentially half the cost.

Full details of this work can be found in

Erin Carson and Nicholas J. Higham, Accelerating the Solution of Linear Systems by Iterative Refinement in Three Precisions MIMS EPrint 2017.24, Manchester Institute for Mathematical Sciences, The University of Manchester, UK, July 2017.