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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Aug 5, 2017 at 23:46
  • 1
    $\begingroup$ The average degree of a planar triangulation is $6,$ so that helps a fair bit. $\endgroup$
    – Igor Rivin
    Commented Aug 6, 2017 at 0:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .