My understanding is that "maximum matching" (or "maximum transversal") are algorithms to pre-order matrix to increase the numerical stability. In Timothy Davis' book Direct Methods for Sparse Linear Systems, 2006, however, this algorithm is put in Chapter 7 which is titled "Fill-reducing ordering". In his more recent paper A survey of direct methods for sparse linear systems, 2016, maximum matching was also placed in section 8 which is titled "Fill-reducing orderings".
So far, my had an impression that reordering algorithms can be categorized into 3 classes:
- for numerical stability: maximum transversal, etc
- for fill-reducing: AMD, etc
- for work-reducing or parallelism-increasing: BTF, BBD, etc
I have problems in understanding putting above 3 classes into a single category called fill-reducing...