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.

$\endgroup$
10
  • $\begingroup$ It seems to be a variant of the Vandermonde matrix. $\endgroup$
    – Pedro Tamaroff
    Dec 17 '12 at 1:30
  • $\begingroup$ @Potato Right. When I say variant I mean it is not in the exact form. $\endgroup$
    – Pedro Tamaroff
    Dec 17 '12 at 1:35
  • 1
    $\begingroup$ @Potato It's not a Vandermonde matrix: the superscripts are identifying the coordinates of the $d$ points $p_1, \dots, p_d$ that are known to lie in the plane--they are not powers. $\endgroup$ Dec 17 '12 at 1:38
  • 1
    $\begingroup$ There is something not clear. Do you perform this task for just one test point $p$ for each set of $d$ points? If not, you find a normal $N$ to the hyperplane and see how $p \cdot N$ compares with $p_1 \cdot N$ for each new $p.$ $\endgroup$
    – Will Jagy
    Dec 17 '12 at 1:53
  • 1
    $\begingroup$ In that case, I would say your actual task is rather more elaborate than a single determinant, and you need to think out what happens when replacing points. $\endgroup$
    – Will Jagy
    Dec 17 '12 at 2:11
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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