About the Author

Applied Algebra and Geometry: A SIAGA of Seven Pictures

By Anna Seigal

The new SIAM Journal on Applied Algebra and Geometry (SIAGA).
SIAM’s brand-new journal, the SIAM Journal on Applied Algebra and Geometry, will feature exceptional research on the development of algebraic, geometric, and topological methods with strong connections to applications. The cover of the new journal shows seven pictures. By describing these pictures and discussing the topics they represent, we hope to give readers a glimpse into the world of algebraic, geometric, and topological problems of interest to applied mathematicians. 

This article is the final installment of a three-part series.

5. Geometric Modeling

The Context

Geometric modeling is an area of applied mathematics that uses piecewise polynomial functions to build computer models that describe shapes in space.

One tool that is used for such modeling is a parametric curve called a Bézier curve, named after the French engineer Pierre Bézier who worked in the automotive industry.

A Bézier curve models smooth motion through time or space. Each curve is defined by a number of control points, which specify its shape and location. These points simplify manipulation of the curve on a computer interface; changing the location of the control points causes a reliable change in the curve.

A collection of \(d+1\) control points \(P_0,\dots,P_d\) defines a Bézier curve of degree \(d.\) The simplest example is when the degree is \(1,\) with two control points \(P_0\) and \(P_1.\) In this case, the Bézier curve is the line that connects the two points 

\[B(t)=(1-t)P_0 + tP_1\]

for \(t\) between \(0\) and \(1.\) A degree \(2\) example is given by

\[B(t)=(1-t)^2P_0+2t(1-t)P_1 + t^2P_2,\]

and in general we have 

\[B(t)= \sum_{i=0}^{d} \binom{d}{i}(1-t)^{d-i}t^{i}P_i.\]

Figure 1. A generalization of a Bézier curve to a two-dimensional Bézier surface. Figure courtesy of [4].
A Bézier curve has a ‘control polygon’ associated with its control points, which is found by taking the line segments connecting adjacent control points. The convex hull of the control polygon contains the curve, and the control polygon has other interesting properties as well. For instance, it can be used in approximation of the original curve.

The Figure

Figure 1 shows a generalization of Bézier curves to a two-dimensional Bézier surface. It is from [4].

Bézier surfaces provide convenient ways to make smooth two-dimensional surfaces, such as for the design of car parts. A Bézier surface is defined in terms of a collection of control points in three-dimensional space

\[\{P_{0,0},\dots,P_{d_{1},d_{2}}\},\]

which now is indexed by two indices rather than one. It is described parametrically by

\[B(t_1,t_2)=\sum_{i_1=0}^{d_1}\sum_{i_2=0}^{d_2} \left( \binom{d_1}{i_1}(1-t_1)^{d_1-i_1}t_1^i\right) \left( \binom{d_2}{i_2}(1-t_2)^{d_2-i_2}t^{i_2}_2 \right) P_{i_1,i_2}. \]

A list of \((d_1+1)(d_2+1)\) control points gives a surface of degree \(d_1d_2\) via this process.

The control points are shown in blue, and the Bézier surface is shown below them in green. We now have a two-dimensional analogue of the control polygon. The surface sits below the convex hull of the control points, which is identified by red lines connecting the blue points. This polyhedral structure connects geometric modeling to polyhedral geometry, described in last month’s installment. 

Applications often demand the investigation of further properties of Bézier curves and surfaces, such as how they intersect with one another. One step in the process is obtaining an implicit formula from a surface’s parametric description. That is, finding the relations amongst the coordinates that are satisfied for all points on the surface. Here, computational algebraic geometry tools are very useful.

6. Tensors

The Context

Figure 2. The Rubik’s Cube is also a cartoon of a tensor of size 3x3x3. Rubik’s Cube® used by permission, Rubik’s Brand Ltd. www.rubiks.com.
Tensors are the higher-dimensional analogues of matrices. They are like matrices, but with three or more dimensions, and are represented by an array of size \(n_1 \times \dotsb \times n_d,\) where \(n_k\) is the number of ‘rows’ in the \(k\)th direction of the array. The entries of the tensor \(A\) are denoted by \(A_{i_1 \dots i_d},\) where \(i_k \in \{1, \dots,n_k\}\) identifies which row in the \(k\)th direction you are viewing. Just as for a matrix, the entries of a tensor are elements in some field, for example real or complex numbers.

Tensors occur naturally when it makes sense to organize data by more than two indices. For instance, if we have a function that depends on three or more discretized inputs \(f(x,y,z)\) where \(x \in \{x_1, \dots, x_{n_1}\},\) \(y \in \{y_1, \dots, y_{n_2}\},\) and \(z \in \{z_1, \dots, z_{n_3}\},\) then we can organize the values of \(A_{ijk} = f(x_i, y_j, z_k)\) into a tensor of size \(n_1 \times n_2 \times n_3.\) Tensors are increasingly widely-used in many applications. This is especially true of signal processing, where the uniqueness of a tensor’s decomposition allows us to find the different signals comprising a mixture. They have also been used in machine learning, genomics, geometric complexity theory, and statistics.

Data analysis techniques are currently limited to a matrix-centric perspective. Tremendous effort to extend the well-understood properties of matrices to the higher-dimensional world of tensors is attempting to overcome this limitation. A greater understanding of tensors paves the way for exciting new developments that can cater to the natural structure of tensor-based data, for example, in experimental design or confounding factor analysis. Such understanding and analysis uses interesting and complicated geometry.

One requirement for computability of a tensor is a good low-rank approximation. Tensors of size \(n_1 \times \dotsb \times n_d\) have \(n_1 \dots n_d\) entries, and this quickly becomes unreasonably large for applications. Matrices can be analyzed via their singular value decomposition, and the best low-rank approximation is obtainable directly from this decomposition by truncating at the \(r\)th largest singular value. For tensors we can also define useful related notions such as eigenvectors, singular vectors, and the higher order singular value decomposition.

The Figure

In addition to depicting the well-known Rubik’s Cube, Figure 2 is a cartoon of a tensor of size \(3 \times 3 \times 3.\) Such a tensor consists of 27 values.

To understand the structure contained in a tensor, we use its natural symmetry group to find a presentation that is simple and structurally transparent. This motivation also underlies the Rubik’s puzzle, although the symmetries can be quite different: a change of basis transformation for the tensor and a permutation of pieces for the puzzle.

Despite being small, a \(3 \times 3 \times 3\) tensor has interesting geometry. A generic tensor of size \(3 \times 3 \times 3\) has seven eigenvectors in \(\mathbb{P}^2.\) We show in [1] that any configuration of seven eigenvectors can arise, provided no six of the seven points lie on a conic.

7. Visualization of Algebraic Varieties

The Context

Figure 3. A Kummer surface has applications in coding theory and cryptography. Image credit: Oliver Labs.
There is a vast mathematical toolbox of techniques that enable understanding of algebraic varieties. It’s great when we can actually draw the algebraic variety in question using visualization software. When possible, this allows us to make the most direct observations.

Although it poses an obvious restriction on the number of dimensions in which we can work, even visualizing particular slices through our variety of interest is structurally revealing. Large polynomials with many terms can be hard to grasp. Modern-day computer tools convert these equations into helpful pictures, aiding comprehension.

The Figure

Figure 3 shows a Kummer surface. It was made by Oliver Labs using the visualization software ‘Surfex.’ Many beautiful pictures have been created in this way: for more, see the picture galleries from the ‘Imaginary: Open Mathematics’ website.

This figure is an example of an irreducible surface in three-dimensional space of degree four. In general, these surfaces have at most 16 singular points. Kummer surfaces are those that attain this upper bound. The 16 singular points represent the \(2\)-torsion points on the Jacobian of the underlying genus \(2\) curve.

Figure 3 also represents the problem-solving areas of coding theory and cryptography, which contain a broad range of applied algebra and geometry. The group law on an elliptic curve is fundamental for cryptography. Similarly, the group law on the Jacobian of hyperelliptic curves has been used for cryptographic purposes (see [2, 3]). The latter is by Kristin Lauter from Microsoft Research, who is president of the Association for Women in Mathematics (AWM).

References

[1] Abo, H., Seigal, A., & Sturmfels, B. (2015). Eigenconfigurations of Tensors. Cornell University Library. Preprint, arXiv:1505.05729.

[2] Bao, F., Samarati, P., & Zhou, J. (2014). Applied Cryptography and Network Security. 12th International Conference, ACNS.

[3] Bos, J., Costello, C., Hisil, H., & Lauter, K. (2013). Fast Cryptography in Genus 2. Advances in Cryptology – Eurocrypt 2013, 7881, 194-210.

[4] García-Puente, L.D., Sottile, F., & Zhu, C. (2011). Toric Degenerations of Bézier Patches, ACM Transactions on Graphics, 30(5).

Anna Seigal is a graduate student at the University of California, Berkeley, working in applied algebra. Her interests lie in tensors and applications to biological data. She enjoys writing about mathematics in terms of pictures, and blogs on this subject at https://picturethismaths.wordpress.com/