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