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...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.