AuthorsJ. Langguth
TitleApproximate weight perfect matchings for pivoting in parallel sparse linear solvers
AfilliationScientific Computing
Project(s)UMOD: Understanding and Monitoring Digital Wildfires
StatusPublished
Publication TypeTalks, invited
Year of Publication2019
Location of TalkInternational Congress on Industrial and Applied Mathematics (ICIAM), Valencia, Spain
Type of TalkInvited Minisymposium Presentation
Abstract

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.

Citation Key26851

Contact person