Nested dissection using quantum annealing
G.A.J. Custers (TU Delft - Electrical Engineering, Mathematics and Computer Science)
RE Kooij – Mentor (TU Delft - Quantum & Computer Engineering)
Stan van der Linde – Graduation committee member (TNO)
Robert Wezeman – Mentor (TNO)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Direct methods to solve systems of equations are a building block of any application involving numerical analysis. While the performance characteristics of dense systems are predictable, sparse systems can have large deviations in running time depending on the order in which Gaussian elimination is applied. Finding the order that results in the lowest running time is in general an NP-Hard problem. Nested dissection is a popular divide and conquer heuristic algorithm used by several numerical solvers. At the heart of nested dissection is the minimum vertex separator problem, an NP-Hard problem. Recent years have seen rapid development of quantum annealers, a class of quantum computers designed to solve optimization problems. This thesis investigates the possible role of quantum annealers as a method to improve elimination orderings produced by nested dissection.