|Title||Approximate weight perfect matchings for pivoting in parallel sparse linear solvers|
|Project(s)||UMOD: Understanding and Monitoring Digital Wildfires|
|Publication Type||Talks, invited|
|Year of Publication||2019|
|Location of Talk||International Congress on Industrial and Applied Mathematics (ICIAM), Valencia, Spain|
|Type of Talk||Invited Minisymposium Presentation|
The problem of finding good pivots in scalable sparse direct solvers before factorization has posed considerable algorithmic challenges in the past. Currently, sequential implementations of maximum weight perfect matching algorithms such MC64 are used due to the lack of alternatives. To overcome this limitation, we propose a fully parallel distributed memory algorithm and show how to derive a factor 2 approximation guarantee. We also discuss a heuristic version that generates perfect matchings of near-optimum weight.