See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/304702520

“Extended Cross-Product” and Solution of a Linear System of Equations

Conference Paper · July 2016

DOI: 10.1007/978-3-319-42085-1_2

CITATIONS READS
6 407

1 author:

Vaclav Skala
University of West Bohemia
310 PUBLICATIONS 2,193 CITATIONS

SEE PROFILE

All content following this page was uploaded by Vaclav Skala on 06 November 2017.

The user has requested enhancement of the downloaded file.

 “Extended Cross-product” and Solution of a Linear
System of Equations

Vaclav Skala1
1
Faculty of Applied Sciences, University of West Bohemia,
Univerzitni 8, CZ 30614 Plzen, Czech Republic
http://www.VaclavSkala.eu

Abstract. Many problems, not only in computer vision and visualization, lead to a system of
linear equations or and fast and robust solution is required. A vast majority of
computational problems in computer vision, visualization and computer graphics are three
dimensional in principle. This paper presents equivalence of the cross–product operation and
solution of a system of linear equations or using projective space representation
and homogeneous coordinates. This leads to a conclusion that division operation for a solution of
a system of linear equations is not required, if projective representation and homogeneous
coordinates are used. An efficient solution on CPU and GPU based architectures is presented with
an application to barycentric coordinates computation as well.

Keywords: Linear system of equations, extended cross-product, projective space computation,

geometric algebra, scientific computation.

1 Introduction
Many applications, not only in computer vision, require a solution of a homogeneous
system of linear equations or a non-homogeneous system of linear
equations . There are several numerical methods used implemented in standard
numerical libraries. However, the numerical solution actually does not allow further
symbolic manipulation. Even more, solutions of equations and are
considered as different problems and especially is not usually solved quite
correctly as users tend to use some additional condition for unknown (usually setting
or so).
In the following, we show the equivalence of the extended cross-product (outer
product or progressive product) with a solution of both types of linear systems of
equations, i.e. and .
Many problems in computer vision, computer graphics and visualization are -
dimensional. Therefore specific numerical approaches can be applied to speed up the
solution. In the following extended cross-product, also called outer product or
progressive product, is introduced in the “classical” notation using symbol.

2 Extended cross product

Let us consider the standard cross-product of two vectors and
. Then the cross-product is defined as:

(1)

where: , .

Skala,V.: “Extended Cross-product” and Solution of a Linear System of Equations,

ICCSA 2016, LNCS 9786, Vol.I, pp.18-35, Springer,
ISBN 978-3-319-42084-4, DOI:10.1007/978-3-319-42085-1_2 , China, 2016
If a matrix form is needed, then we can write:

(2)

In some applications the matrix form is more convenient.

Let us introduce the extended cross-product of three vectors ,
and , as:

(3)

where: , , , .
It can be shown that there exists a matrix form for the extended cross-product
representation:

(4)

where: . In this case and are sub-determinants with columns of the matrix
defined as:
(5)

e.g. sub-determinant etc.

The extended cross-product for -dimensions is defined as:

(6)

where: , , , ,
.
It can be shown that there exists a matrix form as well:

(7)

where . In this case and are sub-determinants with columns of the

matrix defined as:

(8)

e.g. sub-determinant is defined as:

Skala,V.: “Extended Cross-product” and Solution of a Linear System of Equations,

ICCSA 2016, LNCS 9786, Vol.I, pp.18-35, Springer,
ISBN 978-3-319-42084-4, DOI:10.1007/978-3-319-42085-1_2 , China, 2016
 (9)

In spite of the “complicated” description above, this approach leads to a faster

computation in the case of lower dimensions, see Section 7.

3 Projective representation and duality principle

Projective representation and its application for computation are considered to be
mysterious or too complex. Nevertheless we are using it naturally very frequently in
the form of fractions, e.g. . We also know that fractions help us to express values,
which cannot be expressed precisely due to limited length of a mantissa, e.g.
.
In the following we will explore projective representation, actually rational
fractions, and its applicability.

3.1. Projective representation

Projective extension of the Euclidean space is used commonly in computer graphics
and computer vision mostly for geometric transformations. However, in computational
sciences, the projective representation is not used, in general. This chapter shortly
introduces basic properties and mutual conversions. More detailed description of
projective representation and applications can be found in ]12][15][20].
The given point in the Euclidean space is represented in
homogeneous coordinates as , . It can be seen that is actually a
line in the projective space with the origin excluded. Mutual conversions are
defined as:
(10)
where: is the homogeneous coordinate. Note that the homogeneous coordinate
is actually a scaling factor with no physical meaning, while are values with
physical units in general.
The projective representation enables us nearly double precision as the mantissa
of , resp. and are used for a value representation. However we have to distinguish
two different data types, i.e.
 Projective representation of a -dimensional value ,
represented by one dimensional array , e.g. coordinates of
a point, that is fixed to the origin of the coordinate system.
 Projective representation of a -dimensional vector (in the mathematical
meaning) , represented by one dimensional array
. In this case the homogeneous coordinate is actually
just a scaling factor. Any vector is not fixed to the origin of the coordinate
system and it is “movable”.
Therefore a user should take an attention to the correctness of operations. Another
interesting application of the projective representation is the rational trigonometry [19].

Skala,V.: “Extended Cross-product” and Solution of a Linear System of Equations,

ICCSA 2016, LNCS 9786, Vol.I, pp.18-35, Springer,
ISBN 978-3-319-42084-4, DOI:10.1007/978-3-319-42085-1_2 , China, 2016
 3.2. Principle of duality
The projective representation offers also one very important property – principle of
duality. The principle of duality in states that any theorem remains true when we
interchange the words “point” and “line”, “lie on” and “pass through”, “join” and
“intersection”, “collinear” and “concurrent” and so on. Once the theorem has been
established, the dual theorem is obtained as described above [1][5] [14]. In other
words, the principle of duality says that in all theorems it is possible to substitute the
term “point” by the term “line” and the term “line” by the term “point” etc. in and
the given theorem stays valid. Similar duality is valid for as well, i.e. the terms
“point” and “plane” are dual etc. it can be shown that operations “join” a “meet” are
dual as well.
This helps a lot to solve some geometrical problems. In the following we will
demonstrate that on very simple geometrical problems like intersection of two lines,
resp. three planes and computation of a line given by two points, resp. of a plane given
by three points.

4 Solution of
Solution of non-homogeneous system of equation is used in many
computational tasks.
For simplicity of explanation, let us consider a simple example of intersection
computation of two lines a in given as:
(11)
An intersection point of two those lines is given as a solution of a linear system of
equations: :
(12)
Generally, for the given system of liner equations with unknowns in the
form the solution is given:
(13)
where: is a regular matrix having non-zero determinant, the matrix is the
matrix with replaced column by the vector and is a vector of
unknown values.
In a low dimensional case using general methods for solution of linear equations,
e.g. Gauss-Seidel elimination etc., is computational expensive. Also division operation
is computationally expensive and decreasing precision of a solution.
Usually, a condition if then EXIT is taken for solving “close to
singular cases”. Of course, nobody knows, what a value of is appropriate.
5 Solution of
There is another very simple geometrical problem; determination of a line given by
two points and in . This seems to be a quite simple
problem as we can write:
(14)
i.e. it leads to a solution of homogeneous systems of equations , i.e.:

Skala,V.: “Extended Cross-product” and Solution of a Linear System of Equations,

ICCSA 2016, LNCS 9786, Vol.I, pp.18-35, Springer,
ISBN 978-3-319-42084-4, DOI:10.1007/978-3-319-42085-1_2 , China, 2016
 (15)

In this case, we obtain one parametric set of solutions as the Eq.(15) can be multiplied
by any value and the line is the same.
There is a problem – we know that lines and points are dual in the case, so the
question is why the solutions are not dual. However if the projective representation is
used the duality principle will be valid, as follows.

6 Solution and
Let us consider again intersection of two lines a
leading to a solution of non-homogeneous linear system , which is given as:
(16)
If the equations are multiplied by we obtain:
(17)
where: means „projectively equaivalent to“ as and .
Now we can rewrite the equations to the matrix form as :

(18)

where is the intersection point in the homogeneous coordinates.

In the case of computation of a line given by two points given in homogeneous
coordinates, i.e. and , the Eq.(14) is multiplied
by .Then, we get a solution in the matrix form as , i.e.

(19)

Now, we can see that the formulation is leading in the both cases to the same numerical
problem: to a solution of a homogeneous linear system of equations.
However, a solution of homogeneous linear system of equations is not quite
straightforward as there is a one parametric set of solutions and all of them are
projectively equivalent. It can be seen that the solution of Eq. (18), i.e. intersection of
two lines in , is equivalent to:
(20)
and due to the principle of duality we can write for a line given by two points:
(
21)
In the three dimensional case we can use extended cross-product [12][15][16].
A plane given by three points ,
and is determined in the projective
representation as:
(22)
and the intersection point of three planes points ,
and is determined in the projective
representation as:
(23)

Skala,V.: “Extended Cross-product” and Solution of a Linear System of Equations,

ICCSA 2016, LNCS 9786, Vol.I, pp.18-35, Springer,
ISBN 978-3-319-42084-4, DOI:10.1007/978-3-319-42085-1_2 , China, 2016
due to the duality principle.
It can be seen that there is no division operation needed, if the result can be left in the
projective representation. The approach presented above has another one great
advantage as it allows symbolic manipulation as we have avoided numerical solution
and also precision is nearly doubled.

7 Barycentric coordinates computation

Barycentric coordinates are often used in many engineering applications, not only in
geometry. The barycentric coordinates computation leads to a solution of a system of
linear equations. However it was shown, that a solution of a linear system equations is
equivalent to the extended cross product [12][14]. Therefore it is possible to compute
barycentric coordinates using cross product which is convenient for application of SSE
instructions or for GPU oriented computations. Let us demonstrate the proposed
approach on a simple example again.
Given a triangle in defined by points , , the barycentric
coordinates of the point can be computed as follows:

(24)

For simplicity, we set , . It means that we have to solve a system of

linear equations :

(25)

if the points are given in the projective space with homogeneous coordinates
, and . It can be easily proved, due to
the multilinearity, we need to solve a linear system :

(26)

Let us define new vectors containing a row of the matrix and vector as:
(27)
The projective barycentric coordinates are given as:
(28)
i.e.
(29)
Using the extended cross product, the projective barycentric coordinates are given as:

(30)

where , , , .

Skala,V.: “Extended Cross-product” and Solution of a Linear System of Equations,

ICCSA 2016, LNCS 9786, Vol.I, pp.18-35, Springer,
ISBN 978-3-319-42084-4, DOI:10.1007/978-3-319-42085-1_2 , China, 2016
 Similarly in the case, given a tetrahedron in defined by points
, , and the point :
(31)
Then projective barycentric coordinates are given as:
(32)
The Euclidean barycentric coordinates are given as:
(33)
i.e.
(34)

How simple and elegant solution!

The presented computation of barycentric coordinates is simple and convenient for
GPU use or SSE instructions. Even more, as we have assumed from the very
beginning, there is no need to convert projective values to the Euclidean notation. As a
direct consequence of that is, that we are saving a lot of computational time also
increasing robustness of the computation, especially due to division operation
elimination. As a result is represented as a rational fraction, the precision is nearly
equivalent to double mantissa precision and exponent range.
Let us again present advantages of the projective representation on simple
examples.

Fig.1: A line as the intersection of two planes

8 Intersection of two planes

Intersection of two planes and in is seemingly a simple problem, but
surprisingly computationally expensive, Fig.1. Let us consider the “standard” solution
in the Euclidean space and a solution using the projective approach.

Skala,V.: “Extended Cross-product” and Solution of a Linear System of Equations,

ICCSA 2016, LNCS 9786, Vol.I, pp.18-35, Springer,
ISBN 978-3-319-42084-4, DOI:10.1007/978-3-319-42085-1_2 , China, 2016
Given two planes and in :
(35)
where: and are normal vectors of those planes.

Then the directional vector of a parametric line is given by a cross

product:
(36)
and point of the line is given as:

(37)

It can be seen that the formula above is quite difficult to remember and its derivation is
not simple. It should be noted that there is again a severe problem with stability and
robustness if a condition like is used. Also the formula is not convenient
for GPU or SSE applications. There is another equivalent solution based on Plücker
coordinates and duality application, see [12] [16].
Let us explore a solution based on the projective representation explained above.
Given two planes and . Then the directional vector of their intersection is given
as:
(38)
We want to determine the point of the line given as an intersection of those two
planes. Let us consider a plane passing the origin of the coordinate system with the
normal vector equivalent to , Fig.1. This plane is represented as:
(39)
Then the point is simply determined as an intersection of three planes as:
(40)
It can be seen that the proposed algorithm is simple, easy to understand, elegant and
convenient for SEE and GPU applications as it uses vector-vector operations.

Skala,V.: “Extended Cross-product” and Solution of a Linear System of Equations,

ICCSA 2016, LNCS 9786, Vol.I, pp.18-35, Springer,
ISBN 978-3-319-42084-4, DOI:10.1007/978-3-319-42085-1_2 , China, 2016
9 Closest point on the line given as an intersection of two planes
Another example of advantages of the projective notation is finding the closest point on
a line given as an intersection of two planes and to the given point , Fig.2.

Fig.2: The closest point to the given point on an intersection of two planes

A solution in the Euclidean space, proposed in [8], is based on a solution of a system of

linear equations using Lagrange multipliers, leading to a matrix of :

(41)

where: , resp. are points on planes , resp. , with a normal vector , resp. .
Coordinates of the closest point on the intersection of two planes to the
point are given as a solution of this system of linear equations. Note that
the point is given in the Euclidean space.

Let us consider a solution based on the projective representation. The proposed

approach is based on basic geometric transformations with the following steps:
1. Translation of planes , and point so that the point is in
the origin of the coordinate system, i.e. using transformation matrix for the point
translation and matrix for translation of planes [11][14][16].
2. Intersection computation of those two translated planes; the result is a line with the
directional vector and point
3. Translation of the point by inverse translation using the matrix

The translation matrices are defined as:

Skala,V.: “Extended Cross-product” and Solution of a Linear System of Equations,

ICCSA 2016, LNCS 9786, Vol.I, pp.18-35, Springer,
ISBN 978-3-319-42084-4, DOI:10.1007/978-3-319-42085-1_2 , China, 2016
 (42)

If the point is given in the projective space, i.e. , ,

then the matrix is given as .
It can be seen that the computation is more simple, robust and convenient for SSE
or GPU oriented applications. It should be noted that the formula is more general as the
point can be given in the projective space and no division operations are needed.

10 Symbolic manipulations
Symbolic manipulations are very important and help to find or simplify computational
formulas, avoid singularities etc. As the extended cross-product is an associative and
anti-commutative as the cross-product in similar rules are valid, i.e. in :
(43)
In the case of the extended cross-product, i.e. in the projective notation we actually
formally have operations in :
(44)
This can be easily proved by applications of rules for operations with determinants.

However, for general understanding more general theory is to be used – Geometric

Algebra [2][3][4][6][7][10][18], in which the extended cross-product is called outer
product and the above identities are rewritten as:
(45)
where: is an operator of the outer product, which is equivalent to the cross-product
in . There is also an operator for the inner product which is equivalent to the
dot product in .
In geometric algebra geometric product is defined as:
(46)
i.e. in the case of we can write:
(47)
and getting some “strange”, as a scalar and a vector (actually a bivector) are summed
together. But it is a valid result and is called geometric product [18].
However, if the projective representation is used, we need to be a little bit careful
with equivalent operations to the standard operations in the Euclidean space.

Skala,V.: “Extended Cross-product” and Solution of a Linear System of Equations,

ICCSA 2016, LNCS 9786, Vol.I, pp.18-35, Springer,
ISBN 978-3-319-42084-4, DOI:10.1007/978-3-319-42085-1_2 , China, 2016
11 Example of application
Let us consider a simple example in -dimensional space. Assume, that is a
system of linear equations, i.e.:
(48)

and we want to explore , where .

In the “standard” approach a system of linear equations has to be solved
numerically or symbolic manipulation has to be used. We can rewrite the Eq.(48) using
the projective representation as:
(49)

The conversion to the Euclidean space is given as:

(50)
Then using equivalence of the extended cross-product and solution of a linear system
of equations we can write:
(51)
where: , , . It should be
noted that the result is actually in the -dimensional projective space.
In many cases, the result of computation is not necessarily to be converted to the
Euclidean space. If left in the projective representation, we save division operations,
increase precision of computation as the mantissa is actually nearly doubled (mantissa
of and ). Also robustness is increased as well as we haven’t made any specific
assumptions about collinearity of planes. Let a scalar value is given as:
(52)
The scalar value can be expressed as a homogeneous vector in the projective
notation as:
(53)
Generally, the value in the Euclidean space is given as . Extension to the -
dimensional case is straightforward.
As an example let us consider a test if the given point lies on a
plane given by three points using projective notation. A plane is given:
(54)
and the given point has to fulfill condition .
We know that:

(55)

where: , , , . Then, the test

is actually:

Skala,V.: “Extended Cross-product” and Solution of a Linear System of Equations,

ICCSA 2016, LNCS 9786, Vol.I, pp.18-35, Springer,
ISBN 978-3-319-42084-4, DOI:10.1007/978-3-319-42085-1_2 , China, 2016
 (56)

It means that we are getting a bilinear form:

(57)
where: is an antisymmetric matrix with a null diagonal. So we can analyze such
conditions more deeply in an analytical form. It means that we can explore the formula
on a symbolic level. It is also possible to derive some additional information for the
value, resp. value, if the projective notation is used. This approach can be directly
extended do the -dimensional space using geometry algebra [18].

12 Efficiency of computation and GPU Code

Let us consider reliability and the cost of computation of the “standard” approach using
Cramer’s rule using determinants. For the given system of liner equations with
unknowns in the form the solution is given as:
(58)
In the projective notation using homogeneous coordinates we can actually write
, where: and ,
The projective representation not only enables to postpone division operations, but
also offers some additional advantages as follows. Computing of determinants is quite
computationally expensive task. However for 2-4 dimensional cases there are some
advantages using the extended cross-product as explained below.
Tab. 1: Cost of determinant computation
Operation
1 6 24 120
2 12 48 240

Generally the computational expenses are given as:

(59)
Total cost of computation if Cramer’s rule for generalized is used:
Table 2: Cost of cross-product computation
Operation
“ ” 3 27 159
“ ” 6 52 173

Computational expenses for the generalized cross-product matrix based formulation, if

partial intermediate computations are used.
Table 3: Cost of cross-product computation with subdeterminants

3 14 60
6 24 77

Skala,V.: “Extended Cross-product” and Solution of a Linear System of Equations,

ICCSA 2016, LNCS 9786, Vol.I, pp.18-35, Springer,
ISBN 978-3-319-42084-4, DOI:10.1007/978-3-319-42085-1_2 , China, 2016
It means, that for the 2-dimensional and 4-dimensional cases, the expected speed up
is:
(60)
In real implementations on CPU the SSE instructions can be used which are more
convenient for vector-vector operations and some steps can be made in parallel.
Additional speed up can be achieved by GPU use for computation.
In the case of higher dimension modified standard algorithms can be used including
iterative methods [17]. Also as the projective representation nearly doubles precision of
computation, if a single precision on GPU is used (only few processors compute in a
double precision), the result after conversion to the Euclidean representation is
equivalent to the double precision.

13 GPU Code
Many today’s computational systems can use GPU support, which allows fast and
parallel processing. The above presented approach offers significant speed up as the
“standard” cross-product is implemented in hardware as an instruction and the
extended cross-product for 4D can be implemented as:
float4 cross_4D(float4 x1, float4 x2, float4 x3)
{float4 a;
a.x = dot(x1.yzw, cross(x2.yzw, x3.yzw));
a.y = -dot(x1.xzw, cross(x2.xzw, x3.xzw));
a.z = dot(x1.xyw, cross(x2.xyw, x3.xyw));
a.w = -dot(x1.xyz, cross(x2.xyz, x3.xyz));
return a}
In general, it can be seen that a solution of linear systems of equations on GPU for a
small dimension is simple, fast and can be performed in parallel.

14 Conclusion
Projective representation is not widely used for general computation as it is mostly
considered for as applicable to computer graphics and computer vision field only. In
this paper the equivalence of cross-product and solution of linear system of equations
has been presented. The presented approach is especially convenient for -dimensional
and dimensional cases applicable in many engineering and statistical computations,
in which significant speed up can be obtained using SSE instructions or GPU use. Also,
the presented approach enables symbolic manipulation as the solution of a system of
linear equations is transformed to extended cross-product using a matrix form which
enables symbolic manipulations.
Direct application of the presented approach has also been demonstrated on the
barycentric coordinates computation and simple geometric problems.
The presented approach enables avoiding division operations as a denominator is
actually stored in the homogeneous coordinate . It which leads to significant
computational savings, increase of precision and robustness as the division operation is
the longest one and the most decreasing precision of computation.
The presented approach also enables derivation of new and more computationally
efficient formula in other computational fields.

Skala,V.: “Extended Cross-product” and Solution of a Linear System of Equations,

ICCSA 2016, LNCS 9786, Vol.I, pp.18-35, Springer,
ISBN 978-3-319-42084-4, DOI:10.1007/978-3-319-42085-1_2 , China, 2016
 Acknowledgment
The author would like to thank to colleagues at the University of West Bohemia in
Plzen for fruitful discussions and to anonymous reviewers for their comments and hints
which helped to improve the manuscript significantly. Special thanks belong also to
SIGGRAPH and Eurographics tutorials attendee for their constructive questions, which
stimulated this work.
This research was supported by the MSMT CZ - project No. LH12181.

References
1. Coxeter,H.S.M.: Introduction to Geometry, John Wiley, 1961.
2. Doran,Ch., Lasenby,A.: Geometric Algebra for Physicists, Cambridge University Press,
2003
3. Dorst,L., Fontine,D., Mann,S.: Geometric Algebra for Computer Science, Morgan
Kaufmann, 2007
4. Gonzales Calvet,R.: Treatise of Plane Geometry through Geometric Algebra, 2007
5. Hartley,R., Zisserman,A.: MultiView Geometry in Computer Vision, Cambridge
University Press, 2000.
6. Hildenbrand,D.: Foundations of Geometric Algebra Computing, Springer Verlag, , 2012
7. Kanatani,K.: Undestanding geometric Algebra, CRC Press, 2015
8. Krumm,J.: Intersection of Two Planes, Microsoft Research, May 2000
http://research.microsoft.com/apps/pubs/default.aspx?id=68640
9. Johnson,M.: Proof by Duality: or the Discovery of “New” Theorems, Mathematics Today,
December 1996.
10. MacDonald,A.: Linear and Geometric Algebra, Charleston: CreateSpace, 2011
11. Skala,V.: A New Approach to Line and Line Segment Clipping in Homogeneous
Coordinates, The Visual Computer, Vol.21, No.11, pp.905 914, Springer Verlag, 2005
12. Skala,V.: Length, Area and Volume Computation in Homogeneous Coordinates,
International Journal of Image and Graphics, Vol.6., No.4, pp.625-639, 2006
13. Skala,V.: Barycentric Coordinates Computation in Homogeneous Coordinates, Computers
& Graphics, Elsevier, ISSN 0097-8493, Vol. 32, No.1, pp.120-127, 2008
14. Skala,V.: Projective Geometry, Duality and Precision of Computation in Computer
Graphics, Visualization and Games, Tutorial Eurographics 2013, Girona, 2013
15. Skala,V.: Projective Geometry and Duality for Graphics, Games and Visualization -
Course SIGGRAPH Asia 2012, Singapore, ISBN 978-1-4503-1757-3, 2012
16. Skala,V.: Intersection Computation in Projective Space using Homogeneous Coordinates,
Int.Journal on Image and Graphics, ISSN 0219-4678, Vol.8, No.4, pp.615-628, 2008
17. Skala,V.: Modified Gaussian Elimination without Division Operations, ICNAAM 2013,
Rhodos, Greece, AIP Conf.Proceedings, No.1558, pp.1936-1939, AIP Publishing, 2013
18. Vince,J.: Geometric Algebra for Computer Science, Springer, 2008
19. Wildberger,N.J.: Divine Proportions: Rational Trigonometry to Universal Geometry, Wild
Egg Pty, 2005
20. Yamaguchi,F. Computer Aided Geometric Design: A totally Four Dimensional Approach,
Springer Verlag, 2002

Skala,V.: “Extended Cross-product” and Solution of a Linear System of Equations,

ICCSA 2016, LNCS 9786, Vol.I, pp.18-35, Springer,
ISBN 978-3-319-42084-4, DOI:10.1007/978-3-319-42085-1_2 , China, 2016

View publication stats