Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
It seems to be a variant of the Vandermonde matrix. –  Pedro Tamaroff Dec 17 '12 at 1:30
    
@Potato Right. When I say variant I mean it is not in the exact form. –  Pedro Tamaroff Dec 17 '12 at 1:35
1  
@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. –  Jonathan Christensen Dec 17 '12 at 1:38
1  
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.$ –  Will Jagy Dec 17 '12 at 1:53
1  
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. –  Will Jagy Dec 17 '12 at 2:11

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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