A recent survey on direct methods

I have just read a recent survey by

Tim Davis
Sivasankaran Rajamanickam
Wissam Sid-Lakhdar

Timothy A. Davis, Sivasankaran Rajamanickam, and Wissam Sid-Lakhdar,“A survey of direct methods for sparse linear systems (link)”. The authors state their goal in the abstract:

The goal of this survey article is to impart a working knowledge of the underlying theory and practice of sparse direct methods for solving linear systems and least-squares problems, and to provide an overview of the algorithms, data structures, and software available to solve these problems, so that the reader can both understand the methods and know how best to use them.

 

I have very much appreciated the breadth of the survey. It reviews the earlier work on methods for the classical problems (e.g., LU, QR, Cholesky factorizations) and gives the context of the recent work  (e.g., GPU acceleration of the associated software; most recent problems of updating/downdating; exploiting low-rank approximations for efficiency).

One of the most impressive parts of the surveys are their reference lists. This one has 604 bibliographic items  (if I did not do any errors in counting). There is great scholarly work in collecting 604 bibliographic items, reading through them, and putting them into a well-organized survey. There is virtually no bulk references; all citations come with at least a few words. This assiduous approach got me excited and I dug into the reference list. The earliest cited work is from 1957 (one by Berge [1], and one by Markowitz [2]); the latests are from 2015 (there are a number of them).  There are no cited papers from the years 1958, 1959, 1960, 1962, 1964, and 1965. Here is a histogram of the number of papers per 5-year periods (centered at years 1955 to 2015 by increments of 5, e.g., 1955:5:2015).

davisetalCHist

The histogram tells at least two things: (i) much of the activities at the foundations of today’s methods are from the years 1990–2000; (ii) the field is very active, considering that the survey gives an overview of fundamentals, and recent developments which did not fit neatly into the grand/traditional lines of the world of direct methods are only summarized in a relatively short section (Section 12).

I underlined another quotation from the survey:

Well-designed mathematical software has long been considered a cornerstone of scholarly contributions in computational science.

This is a great survey, even for those who know the area. Kudos to Tim, Siva, and Wissam for having crafted it.

References

  1. Claude Berge, Two theorems in graph theory, Proceedings of the National Academy of Sciences of the United States of America 43(9), 842–844, 1957  (link).
  2. Harry M. Markowitz, The elimination form of the inverse and its application to linear programming, Management Science, 3 (3), 255–269, 1957 (link).

On the Birkhoff-von Neumann decomposition

Michele Benzi, Alex Pothen and I have been making use of the celebrated Birkhoff-von Neumann theorem on doubly stochastic matrices. The theorem says that any doubly stochastic matrix can be written as a convex combination of a finitely many permutation matrices. Formally, let \mathbf{A} be a doubly stochastic matrix. Then,

\mathbf{A}=\sum_{j=1}^k \alpha_j \mathbf{P}_j\;,

where \alpha_j>0, \sum_j \alpha_j=1 and each \mathbf{P}_j is a permutation matrix.

Given this formulation, one wonders if the decomposition is unique. Well, the answer is “No”. Then, one asks what can be said about the number k. And this is the main topic of this post.

Richard A. Brualdi [1] discusses many things among which a lower bound and an upper bound on k. The minimum number of permutation matrices is equal to the maximum cardinality of a set of nonzeros positions of \mathbf{A} no two of which could appear together in a single permutation matrix in the pattern of \mathbf{A}. An easy lower bound is then equal to the maximum number of nonzeros in a row or a column of \mathbf{A}. The upper bound is \mathrm{nnz}(\mathbf{A})-2n+2, for a fully indecomposable matrix \mathbf{A} with \mathrm{nnz}(\mathbf{A}) nonzeros; more generally if there are b fully indecomposable blocks, then the upper bound is \mathrm{nnz}(\mathbf{A})-2n+b+1.

What about the minimum number of permutation matrices? It turns out that this is an NP-complete problem. Let’s state it in the form of a standard NP-completeness result.

Input:  A doubly stochastic matrix \mathbf{A}.
Output: A Birkhoff-von Neumann decomposition of \mathbf{A} as \mathbf{A} = \alpha_1\mathbf{P}_1 + \alpha_2\mathbf{P}_2 + \cdots +\alpha_k\mathbf{P}_k.
Measure: The number k of permutation matrices in the decomposition.

The NP-completeness of the decision version of this problem is shown in a recent technical report [2].

References

  1. Richard A. Brualdi, Notes on the Birkhoff algorithm for doubly stochastic matrices, Canadian Mathematical Bulletin, 25(2), 191–199, 1982 (doi).
  2. Fanny Dufossé and Bora Uçar, Notes on Birkhoff-von Neumann decomposition of doubly stochastic matrices, Technical Report, RR-8852, Inria Grenoble Rhône-Alpes, 2016 (link).

More good news

I feel so privileged to be able to post these announcements.

Aydın Buluç
Aydın Buluç

Aydın Buluç, a great scholar and a good friend, has received the IEEE TCSC Award for Excellence for Early Career Researchers. This award recognizes up to three individuals who have made outstanding, influential, and potentially long-lasting contributions in the field of scalable computing within five years of receiving their PhD degree as of January 1 of the year of the award. Aydın received a plaque at the SC15 conference that  was held in Austin, TX in Nov. 15-20, 2015.

Congratulations Aydın!

CSC Mini-symposium at SIAM PP16

SIAM PP16 (April 12-15, 2016 Paris) program just came out. Aydın Buluç, Alex Pothen, and I will be managing a CSC mini-symposium with three parts.

The mini has the following description:

Combinatorial algorithms and tools are used in enabling parallel scientific computing applications. The general approach is to identify performance issues in an application and design, analyze, implement combinatorial algorithms to tackle the identified issues. The proposed minisymposium gathers 12 talks, covering applications in bioinformatics, solvers of linear systems, and data analysis; and graph algorithms for those applications. The objective is to summarize the latest combinatorial algorithmic developments and the needs of the applications. The goal is to cross-fertilize the both domains: the applications will raise new challenges to the combinatorial algorithms, and the combinatorial algorithms will address some of the existing problems of the applications.

The twelve excellent talks are spread out two days: Tuesday April 12, 2016 : The first part at 1:10 PM – 2:50 PM, and the second part at 3:20 PM – 5:00PM; Wednesday April 13, 2016; The third part at 10:35 AM – 12:15 PM.

See you there!

Some great news

We have received some very good news. Three of our colleagues received recognition from two different technical societies.

Umit V. Çatalyürek
Umit V. Çatalyürek

Umit V. Catalyurek and Tim Davis have been elevated to IEEE Fellow. Umit’s elevation included the citation “for contributions to combinatorial scientific computing and parallel computing” and Tim’s included “for contributions to sparse matrix algorithms and software”. This is a great accomplishment as there is a rigorous evaluation procedure.  Here is a link to the complete list of IEEE 2016 Fellows.

Ali Pinar
Ali Pinar

Ali Pinar has been named ACM Distinguished Scientist. This attests his great contributions to the advancement of the science of computing, and to building the knowledge base within the field of computer science. Here is a link to the complete list of ACM Distinguished Members.

 

Here is what Tim says on this occasion:

Tim Davis
Tim Davis

It is really an amazing honor.  IEEE is the first association I joined, way back in the early 80s when I was an undergraduate at Purdue.  So it brings back many fond memories.  I used SPICE in my undergrad days for my circuit simulation homework problems … and now there are circuit simulators out there, commercial and government-lab, that use my solvers.  It’s hard to believe that it’s come full circle, and it’s very encouraging news to hear that I was elected as an IEEE Fellow.  I have had lots to be thankful for this Thanksgiving season (I got the news just days before Thanksgiving).

Congratulations to Umit, Tim and Ali for the recognition!

SIAM Workshop on Combinatorial Scientific Computing (CSC16)

Erik Boman and Assefaw Gebremedhin are organizing the next SIAM Workshop on Combinatorial Scientific Computing (CSC16), to be held in Albuquerque, NM, USA, October 10-12, 2016. Save the date!

Erik and Assefaw led the initiative to produce a proceedings for CSC16. With the help of Cindy Phillips and Bruce Hendrickson they got SIAM to agree to publish an electronic proceedings. We are thrilled for this first official proceedings for a CSC workshop. This will be a great addition to the list of proceedings/collected works on CSC. Here is three of them that I remember:

  • Graph Theory and Computing,
    Ronald C. Read and Claude Berge (Eds), Academic Press, 1972.
  • Graph Theory and Sparse Matrix Computation,
    Alan George, John R. Gilbert, and Joseph W.H. Liu (Eds), IMA Vol. Math. Appl., 56, Springer-Verlag, 1993.
  • Combinatorial Scientific Computing,
    Uwe Naumann and Olaf Schenk (Eds), Chapman & Hall/CRC Computational Science, 2012.

The first two did not have the exact title; they were long before the community decided on the name, but they meant the same thing. Am I missing other similar proceedings/collected works?