10
$\begingroup$

Motivation: determining whether a point $p$ is above or below a plane $\pi$, which is defined by $d$ points, in a $d$-dimensional space, is equivalent to computing the sign of a determinant of a matrix of the form

A = $\begin{pmatrix}p_{1}^{\left(1\right)} & p_{1}^{\left(2\right)} & \cdots & p_{1}^{\left(d\right)} & 1\\ p_{2}^{\left(1\right)} & p_{2}^{\left(2\right)} & \cdots & p_{2}^{\left(d\right)} & 1\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ p_{d}^{\left(1\right)} & p_{d}^{\left(2\right)} & \cdots & p_{d}^{\left(d\right)} & 1\\ p^{\left(1\right)} & p^{\left(2\right)} & \cdots & p^{\left(d\right)} & 1 \end{pmatrix}$

Notes -

  1. When I say sign, I mean either negative, positive, or exactly zero
  2. The entry ${p_i}^j$ means the $j$-coordinate (e.g., $x$, $y$ and $z$ when $d$=3) of the $i$'th point in my problem. The matrix is not a Vandermonde matrix.

The resulting matrix is composed of floating-point numbers. It has no special structure, is not diagonally dominant, is not symmetric, and has no special reason to be positive-semidefinite. It might be sparse, though.

It is, however, many times nearly singular.

I'm interested in computing $\mbox{sign}(|A|)$ in a fast and robust way.

Since this is Math-SE, I'm mainly asking if there are any spectral theorems which allow this computation without explicitly computing the determinant. For example, the Greshgorin Circle Theorem could be very useful if $A$ was diagonally-dominant. Alternatively, any cheap test to identify some cases would also be helpful.

  • 0
    You may wa$n$t to repost this question on [cs.se].2013-02-07

1 Answers 1

0

If the points are nearly coplanar (co-hyperplanar?), then the problem is ill-conditioned. No algorithm you use will give you a "robust" answer in floating-point arithmetic. You can try this for yourself with nearly colinear points in the plane.

That said, there are approaches that are better than others. For example, QR factorization using Householder reflections has attractive stability properties (and a low operation count). By keeping the diagonal of R positive and counting reflections, you can determine the sign of the determinant. See, for example, the Wackypedia article on the QR decomposition.