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
    It seems to be a variant of the Vandermonde matrix.2012-12-17
  • 0
    @Potato Right. When I say variant I mean it is not in the exact form.2012-12-17
  • 0
    @Potato This is not a Vandermonde matrix. See my edit.2012-12-17
  • 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.2012-12-17
  • 0
    I recall a survey on the matter (maybe there is an update) [**Computing the sign or the value of the determinant of an integer matrix, a complexity survey**] by Erich Kaltofen and Gilles Villard (you can find online) and maybe that is worth a look. Regards2012-12-17
  • 0
    @Amzoti I'm familiar with the work, but my entries are floating-point numbers, not integers. Thanks, though!2012-12-17
  • 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.$2012-12-17
  • 0
    @WillJagy (1) depending on the result, one of the points may be replaced (2) computing a normal requires computing the $d$ first-minors of $A$, which is not easier than the original problem, it seems.2012-12-17
  • 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.2012-12-17
  • 0
    You may want 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.