1
$\begingroup$

Suppose the sparsity pattern of $A \in \mathbb{R}^{N \times N}$ is a planar graph. Can I use this to bound the complexity of solving

$$ Ax = b $$ ?

In particular, I was hoping to use the planar separator theorem to produce an elimination ordering that would give an $O(N \sqrt N)$ factorization time.

$\endgroup$
1
$\begingroup$

Yes. As this book chapter (by S. Toledo) shows, the number of arithmetic operations is bounded by the sum over the non-zero columns of the squares of the numbers of nonzero elements therein. The sum of squares of degrees is called "The first Zagreb index", which you can google to gain further enlightenment.

$\endgroup$
  • $\begingroup$ I was actually hoping to use the planarity of the graph to give a tighter lower bound. Perhaps there is a connection here to the first Zagreb index and I'm just not seeing it? $\endgroup$ – Alex Flint Aug 5 '17 at 23:46
  • 1
    $\begingroup$ The average degree of a planar triangulation is $6,$ so that helps a fair bit. $\endgroup$ – Igor Rivin Aug 6 '17 at 0:50

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.