Web: http://www.ima.umn.edu | Email: ima-staff@ima.umn.edu | Telephone: (612) 624-6066 | Fax: (612) 626-7370
Additional newsletters available at http://www.ima.umn.edu/newsletters

IMA Newsletter #367

May 2007

2006-2007 Program

Applications of Algebraic Geometry

See http://www.ima.umn.edu/2006-2007 for a full description of the 2006-2007 program on Applications of Algebraic Geometry.

News and Notes

IMA Expands to the First Floor of Lind Hall

As IMA has grown a great deal in the last few years, we have filled out our available space on the fourth floor of Lind Hall. In response to our request for more space, the university of Minnesota has provided us with two suites of offices on the first floor of Lind Hall. The IMA staff have now mostly relocated to these offices. The future visitors of the IMA can check out an access card from the IMA office in 114 Lind Hall to visit the fourth floor as the doors and elevator accessing the fourth floor are kept locked all day.

IMA Events

IMA Annual Program Year Workshop

Non-Linear Computational Geometry

May 29 - June 2, 2007

Organizers: Ioannis Z. Emiris (National University of Athens), Ron Goldman (Rice University), Thorsten Theobald (Johann Wolfgang Goethe-Universität Frankfurt)
Schedule

Tuesday, May 1

11:15a-12:15pIMA postdoc seminar: TBABenjamin J. Howard (University of Minnesota Twin Cities)Lind Hall 215 PS

Wednesday, May 2

11:15a-12:15pAlgebraic geometry and applications seminar: A homological obstruction to weak order on treesPatricia Hersh (Indiana University)Lind Hall 409 AGS

Thursday, May 3

11:15a-12:15pReal algebraic geometry tutorial: Some applications of real root counting to mechanicsRichard B. Moeckel (University of Minnesota Twin Cities)Lind Hall 409 RAG

Friday, May 4

1:25p-2:25pIMA/MCIM Industrial problems seminar: Pattern discovery in bioinformaticsLaxmi Parida (IBM Thomas J. Watson Research Center)Vincent Hall 1 IPS

Wednesday, May 9

11:15a-12:15pAlexander Yong, University of Minnesota
Algebraic geometry and applications seminar: Schubert combinatorics and geometry
Lind Hall 409 AGS

Thursday, May 10

11:15a-12:15pReal algebraic geometry tutorial: Sums of squares of polynomials Kenneth R. Driessel (Iowa State University)Lind Hall 409 RAG

Tuesday, May 15

1:15p-2:15pAlgebraic geometry and applications seminar: Discriminants, dual varieties and toric geometrySandra Di Rocco (Royal Institute of Technology (KTH))Lind Hall 305 AGS

Wednesday, May 16

Thursday, May 17

11:15a-12:15pReal algebraic geometry tutorial: Sums of squares of polynomials (continued) Kenneth R. Driessel (Iowa State University)Lind Hall 409 RAG

Wednesday, May 23

11:15a-12:15pAlgebraic geometry and applications seminar: On the Newton polytope of specialized resultantsIoannis Z. Emiris (National University of Athens)Lind Hall 409 AGS

Thursday, May 24

11:15a-12:15pReal algebraic geometry tutorial: Numerical polynomial algebraKenneth R. Driessel (Iowa State University)Lind Hall 409 RAG

Monday, May 28

All DayMemorial Day (IMA is closed)

Tuesday, May 29

8:15a-9:00aRegistration and coffeeEE/CS 3-176 W5.29-6.2.07
9:00a-9:15aWelcome and introductionDouglas N. Arnold (University of Minnesota Twin Cities)EE/CS 3-180 W5.29-6.2.07
9:15a-10:05aThe bitstream Descartes methodKurt Mehlhorn (Max-Planck-Institut für Informatik)EE/CS 3-180 W5.29-6.2.07
10:05a-10:40aCoffeeEE/CS 3-176 W5.29-6.2.07
10:40a-11:30aDiscrete geometry processing with topological guaranteesDinesh Manocha (University of North Carolina)EE/CS 3-180 W5.29-6.2.07
11:25a-1:30pLunch W5.29-6.2.07
1:30p-2:00pResultants of polynomials with two separated variablesAndre Galligo (Université de Nice Sophia Antipolis)EE/CS 3-180 W5.29-6.2.07
2:00p-2:30pFast and exact geometric analysis of real algebraic plane curvesNicola Wolpert (Stuttgart University of Applied Sciences)EE/CS 3-180 W5.29-6.2.07
2:30p-3:10pCoffeeEE/CS 3-176 W5.29-6.2.07
3:10p-3:40pThe Voronoi diagram of three linesSylvain Lazard (Institut National de Recherche en Informatique Automatique (INRIA)-Lorraine)EE/CS 3-180 W5.29-6.2.07
3:50p-4:20pSecond ChancesEE/CS 3-180 W5.29-6.2.07
4:20p-4:30pGroup PhotoEE/CS 3-180 W5.29-6.2.07
4:30p-6:30pReception and Poster SessionLind Hall 400 W5.29-6.2.07
Real-time algebraic surface visualizationTor Dokken (SINTEF)
The Voronoi circle of smooth closed curvesIoannis Z. Emiris (National University of Athens)
Arrangements of real algebraic plane curvesMichael Kerber (Max-Planck-Institut für Informatik)
Static balancing of parallel mechanismsBrian Moore (Johann Radon Institute for Computational and Applied Mathematics )
Guided surfacesJorg Peters (University of Florida)
Linkage problems and real algebraic geometryReinhard Steffens (Johann Wolfgang Goethe-Universität Frankfurt)
Real solving bivariate polynomial systems: theory and maple implementationElias P. Tsigaridas (Institut National de Recherche en Informatique Automatique (INRIA))

Wednesday, May 30

8:30a-9:00aCoffeeEE/CS 3-176 W5.29-6.2.07
9:00a-9:50aNew methods for computing the topology of algebraic curves and surfacesBernard Mourrain (Institut National de Recherche en Informatique Automatique (INRIA))EE/CS 3-180 W5.29-6.2.07
9:50a-10:30aCoffeeEE/CS 3-176 W5.29-6.2.07
10:30a-11:00aImplicitization of rational surfaces via linear syzygiesLaurent Busé (Institut National de Recherche en Informatique Automatique (INRIA))EE/CS 3-180 W5.29-6.2.07
11:00a-11:30aOn protocols for the automatic discovery of elementary geometry theoremsTomas Recio (University of Cantabria)EE/CS 3-180 W5.29-6.2.07
11:30a-1:30pLunch W5.29-6.2.07
1:30p-2:00pSextics and spheresCiprian S. Borcea (Rider University)EE/CS 3-180 W5.29-6.2.07
2:30p-3:00pHelly-type theorems for line transversals to disjoint ballsXavier Goaoc (Institut National de Recherche en Informatique Automatique (INRIA)-Lorraine)EE/CS 3-180 W5.29-6.2.07
3:00p-3:30pCoffeeEE/CS 3-176 W5.29-6.2.07
3:30p-4:00pRational convolution surfaces of quadratic Bezier trianglesMartin Peternell (Technische Universität Wien)EE/CS 3-180 W5.29-6.2.07
4:10p-4:40pSecond ChancesEE/CS 3-180 W5.29-6.2.07

Thursday, May 31

8:30a-9:00aCoffeeEE/CS 3-176 W5.29-6.2.07
9:00a-9:50aGeometry and computation of mesh surfaces with planar hexagonal facesWenping Wang (University of Hong Kong)EE/CS 3-180 W5.29-6.2.07
9:50a-10:30aCoffeeEE/CS 3-176 W5.29-6.2.07
10:30a-11:20aRational surfaces with rational offsets and their applications to blending constructionsRimvydas Krasauskas (Vilnius State University)EE/CS 3-180 W5.29-6.2.07
11:20a-1:30pLunch W5.29-6.2.07
1:30p-2:00pReal monoid surfacesRagni Piene (University of Oslo)EE/CS 3-180 W5.29-6.2.07
2:00p-2:30pApproximate implicitization and CAD-type intersection algorithmsTor Dokken (SINTEF)EE/CS 3-180 W5.29-6.2.07
2:30p-3:10pCoffeeEE/CS 3-176 W5.29-6.2.07
3:10p-3:40pGeometric applications of the Bezout matrix in the bivariate tensor-product Lagrange basisLaureano Gonzalez-Vega (University of Cantabria)EE/CS 3-180 W5.29-6.2.07
3:50p-4:20pSecond ChancesEE/CS 3-180 W5.29-6.2.07
6:30p-8:30aGroup Dinner at Caspian BistroCaspian Bistro 2418 University Ave SE Minneapolis, MN 55414 (612) 623-1113 W5.29-6.2.07

Friday, June 1

8:30a-9:00aCoffeeEE/CS 3-176 W5.29-6.2.07
9:00a-9:50aApplication of algebraic geometry to kinematicsManfred Husty (Leopold-Franzens Universität Innsbruck)EE/CS 3-180 W5.29-6.2.07
9:50a-10:30aCoffeeEE/CS 3-176 W5.29-6.2.07
10:30a-11:20aGeometric representation of rigidity-related matroidsIleana Streinu (Smith College)EE/CS 3-180 W5.29-6.2.07
11:20a-1:30pLunch W5.29-6.2.07
1:30p-2:00pGeometric and topological inference in the non linear realm: on the importance of singularity theoryFrederic Cazals (Institut National de Recherche en Informatique Automatique (INRIA))EE/CS 3-180 W5.29-6.2.07
2:00p-2:30pBezier subdivision for inverse molecular kinematicsMing Zhang (University of Texas)EE/CS 3-180 W5.29-6.2.07
2:30p-3:10pCoffeeEE/CS 3-176 W5.29-6.2.07
3:10p-3:40pBezout's theorem and implicitizationCarlos D'Andrea (University of Barcelona)EE/CS 3-180 W5.29-6.2.07
3:50p-4:20pSecond ChancesEE/CS 3-180 W5.29-6.2.07

Saturday, June 2

8:30a-9:00aCoffeeEE/CS 3-176 W5.29-6.2.07
9:00a-9:50aAlgebraic splines for molecular modelingChandrajit L. Bajaj (University of Texas)EE/CS 3-180 W5.29-6.2.07
9:50a-10:30aCoffeeEE/CS 3-176 W5.29-6.2.07
10:30a-11:20aTopics in curve and surface implicitizationDavid A. Cox (Amherst College)EE/CS 3-180 W5.29-6.2.07
11:30a-12:00pSecond Chances and closing remarksEE/CS 3-180 W5.29-6.2.07
Abstracts
Alexander Yong, University of Minnesota
Algebraic geometry and applications seminar: Schubert combinatorics and geometry
Abstract: The topic of Schubert varieties of homogeneous spaces G/P is at the interface between algebraic geometry and combinatorics. I'll describe work on two themes. The first is Schubert calculus: counting points in intersections of Schubert varieties. A goal has been combinatorial rules for these computations. I'll explain the carton rule which manifests basic symmetries of the numbers for the Grassmannian case; this version also has the advantage of generalizing to (co)minuscule G/P. The second concerns singularities of Schubert varieties. I'll give a combinatorial framework for understanding invariant of singularities via a notion we call interval pattern avoidance. The first half of this talk is joint work with Hugh Thomas (U. New Brunswick) while the second half is joint work with Alexander Woo (UC Davis).
Chandrajit L. Bajaj (University of Texas) Algebraic splines for molecular modeling
Abstract: This talk shall describe a survey of algebraic spline (A-spline and A-patch) construction techniques for capturing molecular surfaces and implicit solvation shells (models for molecules in their watery environment). These molecular surfaces are obtained from either atomic 3D coordinates (scattered data) of the molecule, or segmented 3D electron microscopy maps (dense data). For 3D maps at 5- 20 Angstrom resolution, I shall also present algebraic spline algorithms to detect and represent secondary (helices, sheets) and/or tertiary (sandwiches, barrels, etc.) structural molecular models. For these latter algorithms, we employ techniques from computational algebraic geometry and differential topology, especially the computation of stable/unstable manifolds of certain critical points of distance functions of molecular surface boundaries.
Ciprian S. Borcea (Rider University) Sextics and spheres
Abstract: A generic configuration of three spheres determines several sextic curves, all related to the curve of common tangents. First among them, the direction-sextic, which records only the direction of these tangents, retains in fact, as a planar projective complex curve, enough information for reconstructing the sphere configuration, up to similarity. I shall discuss properties of this family of sextics and the resulting criterion for classifying configurations.
Laurent Busé (Institut National de Recherche en Informatique Automatique (INRIA)) Implicitization of rational surfaces via linear syzygies
Abstract: Surface implicitization, i.e. finding the implicit equation of an algebraic surface defined parametrically, is a classical problem and there are numerous approaches to its solution. In this talk, we will show that the linear syzygies of the parametrization of a rational surface can be used to represent and to compute its implicit equation under suitable conditions. This is, in some sense, a natural generalization of the well-known method of "moving curves" for plane curve implicitization.
Peter Bürgisser (Universität-GHS Paderborn) Algebraic geometry and applications seminar: Average volume, curvatures, and Euler characteristic of random real algebraic varieties
Abstract: We determine the expected curvature polynomial of random real projective varieties given as the zero set of independent random polynomials with Gaussian distribution, whose distribution is invariant under the action of the orthogonal group. In particular, the expected Euler characteristic of such random real projective varieties is found. This considerably extends previously known results on the number of roots, the volume, and the Euler characteristic of the solution set of random polynomial equations.
Frederic Cazals (Institut National de Recherche en Informatique Automatique (INRIA)) Geometric and topological inference in the non linear realm: on the importance of singularity theory
Abstract: In the non linear realm, a powerful way to describe complex shapes is in terms of stratifications, that is topological disks together with the proper incidences, so as to define some kind of complex (cell, CW, etc). In particular, singularity theory provides a convenient way to specify such incidences through local normal forms, the parametric form of the topological disks depending on the particular problem investigated. We shall review two examples illustrating this framework in 3D : the detection of loci of extremal curvature of smooth surfaces (the so-called ridges), and the calculation of the Morse-Smale complex of the distance function to points in 3D space (the so-called flow complex). We shall conclude with perspectives arising in trying to generalize such approaches in higher dimension.
David A. Cox (Amherst College) Topics in curve and surface implicitization
Abstract: This lecture will discuss several topics related to curve and surface implicitization, including the structure of the moving curve ideal, the construction of mu-bases for surface implicitizations, and the resultant of the mu-basis.
Carlos D'Andrea (University of Barcelona) Bezout's theorem and implicitization
Abstract: This is a joint work with Martin Sombra. The computation of the implicit equations of polynomial and rational parametrizations is always a hot topic in Computational Algebraic Geometry and CAGD. Recently, a lot of attention has been given to the computation of the Newton Polytope of the implicit equation, given the supports of the parametrization (sparse philosophy). In this talk, we will show how the use of classical intersection theory in the torus can give us non-trivial information about this Newton Polytope. As an application of these results, we can give a complete description of the Newton Polytope of the implicit equation of a generic plane rational curve.
Sandra Di Rocco (Royal Institute of Technology (KTH)) Algebraic geometry and applications seminar: Discriminants, dual varieties and toric geometry
Abstract: Given an algebraic variety, embedded in projective space, the closure of all hyperplanes tangent at some non singular point is called the dual variety. A general embedding has dual variety of co-dimension one (in the dual projective space) and hence defined by an irreducible homogeneous polynomial, called the discriminant. The study of the exceptional embeddings, i.e. the ones having dual variety of lower dimension, is a very classical problem in algebraic geometry, still open for many classes of varieties. I will explain the problem and give the solution for the class of non singular toric varieties.
Tor Dokken (SINTEF) Approximate implicitization and CAD-type intersection algorithms
Abstract: When developing CAD-type intersection algorithms for NonUniform Rational B-splines surfaces (NURBS) is important to ensure that the algorithm identifies all intersection branches. For transversal intersections this is fairly straight forward. For singular or near singular intersection, when the surfaces are close and near parallel, the traditional approach of recursive subdivision does not suffice on its own. The use of algebraic surfaces to separate near parallel not intersecting surfaces reduces the depth of recursion. Approximate implicitization denotes methods that approximate piecewise parametric manifolds p(s) with an algebraic hypersurface q(x)=0. The talk will address the approach to approximate implicitization already published by the author and further report on how approximate implicitization has helped the development of a CAD-type intersection algorithms addressing self-intersecting CAD-surfaces, and singular and near singular intersection of NURBS surfaces.
Kenneth R. Driessel (Iowa State University) Real algebraic geometry tutorial: Numerical polynomial algebra
Abstract: See the book "Numerical Polynomial Algebra" by H. J. Stetter, SIAM, 2004.
Ioannis Z. Emiris (National University of Athens) The Voronoi circle of smooth closed curves
Abstract: Voronoi diagrams in the plane are fundamental objects in computational geometry. We wish to extend their study to nonlinear objects, such as ellipses, under the Euclidean distance. From the point of view of algebraic complexity, the bottleneck is in computing the Voronoi circle of 3 objects. We present a subdivision scheme that approximates, to any desired accuracy, the Voronoi circle of 3 smooth parametric closed curves. It exploits the underlying geometry to achieve quadratic convergence. The algorithm has been implemented and experimental results are shown.
Andre Galligo (Université de Nice Sophia Antipolis) Resultants of polynomials with two separated variables
Abstract: The intersection curve C of two surfaces parameterized by polynomials is defined by 3 equations:

F(s,t) = G(u,v)

and its geometry can be studied via its projection E on the (s,u)-space. The equation of E is obtained by elimination of the two separated variables t and v. This is done by the computation of a special bi-variate resultant. I will present this new resultant which was introduced in a joint paper with L. Buse and M. Elkadi and further studied in a joint work with M. Elkadi.
Xavier Goaoc (Institut National de Recherche en Informatique Automatique (INRIA)-Lorraine) Helly-type theorems for line transversals to disjoint balls
Abstract: Helly's theorem of 1923 opened a large field of inquiry now designated as geometric transversal theory. A typical concern is the study of all k-planes (also called k-flats) that intersect all elements of a given family of subsets (or objects) in Rd. These are the k-transversals of the given family and they define a certain subspace of the corresponding Grassmannian. I will present recent results on Helly-type theorems for the existence of line transversals to disjoint balls obtained in collaboration with Ciprian Borcea, Otfried Cheong, Andreas Holmsen and Sylvain Petitjean.
Laureano Gonzalez-Vega (University of Cantabria) Geometric applications of the Bezout matrix in the bivariate tensor-product Lagrange basis
Abstract: Using a new formulation of the Bezout matrix, we construct bivariate matrix polynomials expressed in a tensor-product Lagrange basis. We use these matrix polynomials to solve common tasks in computer-aided geometric design: for example, we show that these bivariate polynomials can serve as stable and efficient implicit epresentations of plane curves for a variety of curve intersection problems including offset manipulation. This is a joint work with D. Aruliah, R. Corless and A. Shakoori
Patricia Hersh (Indiana University) Algebraic geometry and applications seminar: A homological obstruction to weak order on trees
Abstract: When sorting data on a network of computers, it is natural to ask which data swaps between neighbors constitute progress. In a linear array, the answer is simple, by virtue of the fact that permutations admit pleasant notions of inversions and weak order. I will discuss how the topology of chessboard complexes constrains the extent to which these ideas may carry over to other trees; it turns out that there are homological obstructions telling us that a tree does not admit an inversion function unless each node has at least as much capacity as its degree minus one. On the other hand, we construct an inversion function and weak order for all trees that do meet this capacity requirement, and we prove a connectivity bound conjectured by Babson and Reiner for `Coxeter-like complexes' along the way.
Manfred Husty (Leopold-Franzens Universität Innsbruck) Application of algebraic geometry to kinematics
Abstract: Algebraic methods in connection with classical multidimensional geometry have proven to be very efficient in the computation of direct and inverse kinematics of mechanisms as well as the explanation of strange, pathological behaviour of mechanical systems. Generally one can say that every planar, spherical or spatial mechanism having revolute or prismatic joints can be described by systems of algebraic equations. In this talk we give an overview of the results achieved within the last years using algebraic geometric methods, geometric preprocessing and numerical analysis. We provide the mathematical and geometrical background, like Study's parametrization of the Euclidean motion group, the ideals belonging to mechanism constraints The methods are explained with different examples from mechanism analysis and synthesis.
Michael Kerber (Max-Planck-Institut für Informatik) Arrangements of real algebraic plane curves
Abstract: We present a complete and exact algorithm for computing the arrangement of algebraic curve segments, based on the generic sweep-line algorithm from Bentley and Ottmann. We do not impose any condition on the degree or the geometry of the curves defining the arrangement. The predicates for the sweep-line algorithm are all reduced to the {\em Curve analysis} (compute the topology and critical point locations of one curve) and the {\em Curve pair analysis} (compute the geometry of a pair of curves, in particular find their real intersections). Only few exact information is precalculated using subresultants and Sturm-Habicht sequences; numerical methods both speed-up the analysis of curves and curve pairs in generic cases, and also find non-generic cases during the analysis. Non-generic positions are transformed to generic ones by a change of coordinates, but a subsequent back-transformation provides the results in the original coordinate system. A preliminary version of the algorithm has been implemented in the EXACUS-library AlciX. (joint work with Arno Eigenwillig)
Rimvydas Krasauskas (Vilnius State University) Rational surfaces with rational offsets and their applications to blending constructions
Abstract: A surface offsetting operation in CAGD (Computer Aided Geometric Design) involves sophisticated approximation techniques, since an offset of a general rational surface is not rational. On the other hand, a class of rational surfaces with rational offsets (PN-surfaces) includes main primitive surfaces in CAGD: i.e. natural quadrics (sphere, circular cylinders and cones), torus, and also their generalizations: Dupin cyclides and rational canal surfaces. Therefore, it is important to understand what geometric modeling constructions are possible if only PN-surfaces are used, and what is their lowest parametrization degree. We follow Laguerre geometric approach to the theory of PN-surfaces and use a universal rational parametrization of the Blaschke cylinder. This allows us to generate new low degree analytic solutions for PN-surface blendings between the following pairs: plane/natural quadric, two natural quadrics and natural quadric/Dupin cyclide. Applications will be illustrated by recent implementations in a commercial CAD software package.
Sylvain Lazard (Institut National de Recherche en Informatique Automatique (INRIA)-Lorraine) The Voronoi diagram of three lines
Abstract: We give a complete description of the Voronoi diagram of three lines in three-dimensional real space. In particular, we show that the topology of the Voronoi diagram is invariant for three lines in general position, that is, that are pairwise skew and not all parallel to a common plane. The trisector consists of four unbounded branches of either a non-singular quartic or of a cubic and line that do not intersect in real space. Each cell of dimension two consists of two connected components on a hyperbolic paraboloid that are bounded, respectively, by three and one of the branches of the trisector. The proof technique, which relies heavily upon modern tools of computer algebra, is of interest in its own right. This characterization yields some fundamental properties of the Voronoi diagram of three lines. In particular, we present linear semi-algebraic tests for separating the two connected components of each two-dimensional Voronoi cell and for separating the four connected components of the trisector. This enables us to answer queries of the form, given a point, determine in which connected component of which cell it lies. We also show that the arcs of the trisector are monotonic in some direction. These properties imply that points on the trisector of three lines can be sorted along each branch using only linear semi-algebraic tests.
Dinesh Manocha (University of North Carolina) Discrete geometry processing with topological guarantees
Abstract: Our goal is to compute reliable solutions for many non-linear geometric problems that arise in geometric modeling, computer graphics and robotics. Prior methods for solving these problems can be classified into exact and approximate approaches. The exact algorithms are able to guarantee correct output, but are usually difficult to implement reliably and efficiently. On the other hand, current approximate techniques may not provide any topological guarantees on the solution. We bridge the gap between these two approaches, by developing a unified sampling based approach to solve these problems with topological guarantees. Specifcally, we present results for surface extraction and motion planning problems. Surface extraction problems include Boolean operations, implicit surface polygonization and Minkowski sum evaluation. We compute an approximate boundary of the final solid defined by these operations. Our algorithm computes an approximation that is guaranteed to be topologically equivalent to the exact surface and bounds the approximation error using two-sided Hausdorff error. We demonstrate the performance of our approach for the following applications: Boolean operations on complex polyhedral models and low degree algebraic primitives, model simplification and remeshing of polygonal models, and Minkowski sums and offsets of complex polyhedral models. The second class of problems is motion planning of rigid or articulated robots translating or rotating among stationary obstacles. We present an algorithm for complete motion planning, i.e., find a path if one exists and report a failure otherwise. Our algorithm performs deterministic sampling to compute a roadmap that captures the connectivity of the free space and combines with randomized sampling and cell decomposition to further improve the performance. We demonstrate the performance of our algorithm on a number of challenging environments with narrow passages and no collision-free paths.
Kurt Mehlhorn (Max-Planck-Institut für Informatik) The bitstream Descartes method
Abstract: The Descartes method is an algorithm for isolating the real roots of square-free polynomials with real coefficients. We assume that coefficients are given as (potentially infinite) bit-streams. In other words, coefficients can be approximated to any desired accuracy, but are not known exactly. We show that a variant of the Descartes algorithm can cope with bit-stream coefficients. To isolate the real roots of a square-free real polynomial q(x) of degree n, root separation ρ, coefficients bounded by 2 to the τ, and leading coefficient at least one, the algorithm needs coefficient approximations with O(n(log(1/ρ) + τ)) bits after the binary point and has an expected cost of O(n4 (log(1/ρ) + τ)2) bit operations. We also report on computational experience with the algorithm.
Richard B. Moeckel (University of Minnesota Twin Cities) Real algebraic geometry tutorial: Some applications of real root counting to mechanics
Abstract: This talk is intended to illustrate some of the methods covered last semester in the real algebraic geometry tutorial. I will describe some problems from celestial mechanics which can be reduced to counting real roots of systems of polynomial equations. I will show how to solve some of the simplest ones by using Sturm's algorithm and Hermite root counting and will mention several open problems.
Brian Moore (Johann Radon Institute for Computational and Applied Mathematics ) Static balancing of parallel mechanisms
Abstract: The design of statically balanced mechanisms consists of deriving a set of constraints betweeen kinematic and static parameters such that the center of mass remains fixed for any configuration of the mechanism. Such structures have several practical applications, including the elimination of vibrations which improved both precision and performance. Using the four-bar mechanism as an example, we formulate the kinematic constraints between the angles and the static balancing constraints as algebraic equations over real and complex variables. This reduces to the problem of the factorization of Laurent polynomials which can be solved using Newton polytopes and Minkowsi sums. Finally, we determine necessary and sufficient conditions for statically balanced four-bar mechanisms. This is a joint work with Josef Schicho and Clement Gosselin.
Bernard Mourrain (Institut National de Recherche en Informatique Automatique (INRIA)) New methods for computing the topology of algebraic curves and surfaces
Abstract: Computing the topology of a geometric object defined implicitly appears in many geometric modeling problems, such as surface-surface intersection, self-intersection, arrangement computation problems ... It is a critical step in the analysis and approximation of (semi-)algebraic curves or surfaces, encountered in these geometric operations. Its difficulties are mainly due to the presence of singularities on these algebraic objects and to the analysis of the geometry near these singular points. The classical approach which has been developed for algebraic curves in the plane projects the problem onto a line, detects the value which are critical for this projection and lift points back on the curve at these critical values and in between. Information on the number of branches at these critical values or genericity condition tests on the number of critical points above a value of the projection have to be computed, in order to be able to perform correctly the combinatorial connection step of these algorithms. This approach has also been extended to curves and surfaces in 3D. In the talk, we will consider methods which requires information on the boundary of regions instead of information at critical points. We will describe a new method for computing the topology of planar implicit curves, which proceed by subdivision and which only requires the isolation of extremal points. Extension of this approach to curves and surfaces in 3D will be described. Experimentation of these algorithms based on the subdivision solvers of the library SYNAPS and the algebraic-geometric modeler AXEL will shortly demonstrated.
Laxmi Parida (IBM Thomas J. Watson Research Center) IMA/MCIM Industrial problems seminar: Pattern discovery in bioinformatics
Abstract: In this talk we look at the combinatorics and statistics of patterns that computational biologists discover at different levels in biological data be it nucleic acid sequence, microarray data or other formal structures. Is there a commonality that runs across these various domains? Can we apply the lessons learned in one domain in another? In this talk we focus on an interesting class of patterns called permutation patterns. We apply these mathematical structures to some problems arising naturally in the area of computational biology such as the problem of common gene clusters across species, phylogeny within populations, and the task of modeling complex control of transcriptions via motifs. In each of these cases we identify the underlying mathematical problems and show some promising results of applying the proposed solutions to biological data. We also discuss the problem of formulating and computing the statistical significance of the permutations motifs in the different domains.
Martin Peternell (Technische Universität Wien) Rational convolution surfaces of quadratic Bezier triangles
Abstract: In the present talk it will be shown that polynomial quadratic triangular Bezier surfaces are LN-surfaces which means that their normal vector field n(u,v) can be parametrized by linear coordinate functions. The close relation to quadratic Cremona transformations in the parameter domain is elucidated. These reparameterizations can be used for the computation of convolution surfaces.
Jorg Peters (University of Florida) Guided surfaces
Abstract: Guided surface construction separates the conceptual design and the representation by prescribing local shape via guide surfaces and then sampling these guides with a finite number of tensor-product patches. This approach yields C2 subdivision surfaces and polynomial C2 surfaces, typically with good curvature distribution.
Ragni Piene (University of Oslo) Real monoid surfaces
Abstract: A monoid surface is a surface of degree d which has a singular point of multiplicity d-1. Any monoid surface admits a rational parameterization, hence is of potential interest in computer aided geometric design. The possible real forms of the singularities on a monoid surface are determined. These results are applied to the classification of quartic monoid surfaces and a study of a stratification of the parameter space of these surfaces. A part of this work is joint with M. Løberg and P.H. Johansen, the other part is due to P.H. Johansen.
Tomas Recio (University of Cantabria) On protocols for the automatic discovery of elementary geometry theorems
Abstract: Joint work with work with G. Dalzotto and A. Montes. In the talk we will deal with automatic discovery of elementary geometry theorems, through the algebraic geometry framework that has already shown its success for automatic theorem proving. Automatic discovery of theorems addresses the case of statements that are false in most relevant cases. It aims to produce, automatically, complementary hypotheses for the given statement to become correct. For example, we can draw a triangle and, then, the feet of the corresponding altitudes. These feet are the vertices of a new triangle, the so called "orthic" triangle for the given triangle. We want this orthic triangle to be equilateral, but it is not so, in general. Thus we impose as a thesis that the orthic triangle is equilateral and we expect our method to find the more general situations in which this is going to happen. In the talk we do not start providing a method, but stating a general framework for discovery, a kind of general protocol. Namely, we begin collecting the conditions that a couple of ideals, each one belonging to different set of variables–ideally related to the degrees of freedom of the geometric situation–, should verify in order to express necessary and sufficient conditions for the given thesis to hold. Such couple of ideals (named here as a FSDIC) will contribute for some extra hypothesis of equality (respectively, of inequality) type that are required for the theorem to hold. It will be shown, through examples, that such couple does not always exist (and it is, in general, not unique). But, if it exists, then we can identify and construct a particular FSDIC, that turns out to be very close to the output of the method presented in Recio-Velez, Journal of Automated Reasoning, 23, (1999). A test for the existence of a FSDIC will be then stated. Next we will explore the meaning of FSDIC for wise choices of variables (ie. when we deal with "interesting" variables), but we will also remark its limitations in other contexts. We will show how the inclusion "a priori", as part of the hypotheses, of some non-degeneracy conditions, could help computing through the discovery protocol we are considering. And, then, we will observe how this inclusion can be done through two (apparently similar) methods, but that the choice of one or the other has, sometimes, different consequences and requires human decision. Finally we will exhibit a collection of examples achieved via different methods, including, in particular, the use of Montes' MCCGS (minimal canonical comprehensive Groebner basis), that yields some results surprisingly close to our geometric intuition.
Reinhard Steffens (Johann Wolfgang Goethe-Universität Frankfurt) Linkage problems and real algebraic geometry
Abstract: Joint work with Thorsten Theobald. Linkages are graphs whose edges are rigid bars, and they arise as a natural model in many applications in computational geometry, molecular biology and robotics. Studying linkages naturally leads to a variety of questions in real algebraic geometry, such as:
  1. Given a rigid graph with prescribed edge lengths, how many embeddings are there?
  2. Given a 1-degree-of-freedom linkage, how can one characterize and compute the trajectory of the vertices?
From the real algebraic point of view, these questions are questions of specially-structured real algebraic varieties. On the poster we exhibit some techniques from sparse elimination theory to analyze these problems. In particular, we show that certain bounds (e.g. for Henneberg-type graphs) naturally arise from mixed volumes and Bernstein's theorem.
Ileana Streinu (Smith College) Geometric representation of rigidity-related matroids
Abstract: Sparsity matroids generalize the combinatorics behind several types of rigidity (2D bar-and-joint, arbitrary dimension body-and-bar, etc.). A conspicuous open problem is to find geometric representations for ALL of them. We present some partial answers. This is joint work with Louis Theran from UMass Amherst.
Elias P. Tsigaridas (Institut National de Recherche en Informatique Automatique (INRIA)) Real solving bivariate polynomial systems: theory and maple implementation
Abstract: We present three projection-based algorithms for exact real solving of well-constrained, bivariate systems of relatively prime polynomials. Using recent advances in univariate real root isolation and extending fast algorithms of subsresultant sequences to several variables we derive a complexity bound of O(N12), where N bounds the degree and the bitsize of the polynomials, improving the previously known bound by two factors. In the same complexity bound we can also compute the topology of a real plane algebraic curve. We also present a MAPLE implementation of the algorithms, that also provides univariate real root isolation and basic operations with real algebraic numbers.
Wenping Wang (University of Hong Kong) Geometry and computation of mesh surfaces with planar hexagonal faces
Abstract: Joint work with Yang Liu. Motivated by applications in modeling glass structures in architecture, we consider the geometry and computation of mesh surfaces with planar hexagonal faces from the point of view of discrete differential geometry. It is shown that the mesh structure is naturally related to conjugate curve networks on its underlying smooth surface; furthermore, the shape of each hexagonal face is in the limit related to the Dupin indicatrix. These results are used in combination with an optimization method to compute a mesh surface with planar hexagonal faces to approximate a given smooth surface.
Nicola Wolpert (Stuttgart University of Applied Sciences) Fast and exact geometric analysis of real algebraic plane curves
Abstract: An algorithm is presented for the geometric analysis of an algebraic curve f (x,y) = 0 in the real affine plane. It computes a cylindrical algebraic decomposition (CAD) of the plane, augmented with adjacency information. The adjacency information describes the curve’s topology by a topologically equivalent planar graph. The numerical data in the CAD gives an embedding of the graph. The algorithm is designed to provide the exact result for all inputs but to perform only few symbolic operations for the sake of efficiency. In particular, the roots of f (a,y) at a critical x-coordinate a are found with adaptive-precision arithmetic in all cases, using a variant of the Bitstream Descartes method (Eigenwillig et al., 2005). The algorithm may choose a generic coordinate system for parts of the analysis but provides its result in the original system. The algorithm has been implemented as C++ library AlciX in the EXACUS project. Running time comparisons with top by Gonzalez-Vega and Necula (2002), and with cad2d by Brown demonstrate its efficiency.
Ming Zhang (University of Texas) Bezier subdivision for inverse molecular kinematics
Abstract: Conformational searching is a core task in inverse molecular kinematics. Algorithmic improvements affecting either the speed or quality of conformational searching will have a profound impact on applications including ligand-receptor docking, ab initio prediction of protein structure, and protein folding. In this talk, we focus on a specific geometry-constrained conformational searching problem, where some feature atoms have pre-specified target positions. Using Bezier subdivision, we present a method to locate and approximate the solutions of the equations derived from constraints on the feature atoms. The conformations corresponding to these solutions are all the conformations satisfying the target constraints. Three implementations of the subdivision method taking advantage of the sparsity of the coefficients of the polynomial equations are presented and the results are compared.
Visitors in Residence
Pankaj Kumar Agarwal Duke University 5/28/2007 - 6/2/2007
Jungha An University of Minnesota Twin Cities 9/1/2005 - 8/31/2007
Douglas N. Arnold University of Minnesota Twin Cities 7/15/2001 - 8/31/2007
Donald G. Aronson University of Minnesota Twin Cities 9/1/2002 - 8/31/2007
Chandrajit L. Bajaj University of Texas 5/28/2007 - 6/2/2007
Hélène Barcelo Arizona State University 5/7/2007 - 6/1/2007
Saugata Basu Georgia Institute of Technology 4/4/2007 - 6/30/2007
Daniel J. Bates University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Arend Bayer University of Utah 5/8/2007 - 5/11/2007
Yermal Sujeet Bhat University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Ciprian S. Borcea Rider University 5/28/2007 - 6/2/2007
Peter Bürgisser Universität-GHS Paderborn 4/11/2007 - 5/18/2007
Laurent Busé Institut National de Recherche en Informatique Automatique (INRIA) 5/27/2007 - 6/3/2007
Frederic Cazals Institut National de Recherche en Informatique Automatique (INRIA) 5/28/2007 - 6/3/2007
Ionut Ciocan-Fontanine University of Minnesota Twin Cities 9/1/2006 - 6/30/2007
David A. Cox Amherst College 5/28/2007 - 6/2/2007
Carlos D'Andrea University of Barcelona 5/29/2007 - 6/8/2007
Alicia Dickenstein University of Buenos Aires 5/23/2007 - 6/2/2007
Jintai Ding University of Cincinnati 5/27/2007 - 6/2/2007
Sandra Di Rocco Royal Institute of Technology (KTH) 4/4/2007 - 6/4/2007
Tor Dokken SINTEF 5/28/2007 - 6/3/2007
Kenneth R. Driessel Iowa State University 9/1/2006 - 6/29/2007
Fayssal El Moufatich Vodafone Group R&D Germany 5/28/2007 - 6/2/2007
Ioannis Z. Emiris National University of Athens 5/2/2007 - 6/2/2007
Makan Fardad University of Minnesota Twin Cities 8/26/2006 - 8/13/2007
Michael S. Floater University of Oslo 5/28/2007 - 6/2/2007
Andre Galligo Université de Nice Sophia Antipolis 5/28/2007 - 6/4/2007
Luis Garcia-Puente Texas A & M University 5/29/2007 - 6/3/2007
Xavier Goaoc Institut National de Recherche en Informatique Automatique (INRIA)-Lorraine 5/26/2007 - 6/2/2007
Ron Goldman Rice University 5/28/2007 - 6/3/2007
Laureano Gonzalez-Vega University of Cantabria 5/21/2007 - 6/9/2007
Jason E. Gower University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Milena Hering University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Patricia Hersh Indiana University 2/15/2007 - 5/15/2007
Christopher Hillar Texas A & M University 5/28/2007 - 6/6/2007
Benjamin J. Howard University of Minnesota Twin Cities 9/1/2006 - 8/21/2007
Evelyne Hubert Institut National de Recherche en Informatique Automatique (INRIA) 9/1/2006 - 6/30/2007
Manfred Husty Leopold-Franzens Universität Innsbruck 5/28/2007 - 6/3/2007
Farhad Jafari University of Wyoming 9/1/2006 - 6/30/2007
Ravi Janardan University of Minnesota Twin Cities 5/29/2007 - 6/2/2007
Itnuit Janovitz-Freireich North Carolina State University 5/29/2007 - 6/2/2007
Anders Nedergaard Jensen Aarhus University 9/6/2006 - 6/30/2007
Gabriela Jeronimo University of Buenos Aires 4/15/2007 - 6/9/2007
Steve Kaliszewski Arizona State University 1/7/2007 - 6/30/2007
Mordechai Katzman University of Sheffield 1/10/2007 - 5/15/2007
Michael Kerber Universität Kaiserslautern 2/19/2007 - 5/11/2007
Michael Kerber Max-Planck-Institut für Informatik 5/27/2007 - 6/3/2007
Michael Kettner Georgia Institute of Technology 5/28/2007 - 6/6/2007
John Keyser Texas A & M University 5/28/2007 - 6/2/2007
Rimvydas Krasauskas Vilnius State University 5/20/2007 - 6/20/2007
Song-Hwa Kwon University of Minnesota Twin Cities 8/30/2005 - 8/31/2007
Oliver Labs Universität des Saarlandes 5/28/2007 - 6/3/2007
Niels Lauritzen Aarhus University 8/28/2006 - 7/10/2007
Sylvain Lazard Institut National de Recherche en Informatique Automatique (INRIA)-Lorraine 5/28/2007 - 6/3/2007
Anton Leykin University of Minnesota Twin Cities 8/16/2006 - 8/15/2007
Hstau Y Liao University of Minnesota Twin Cities 9/2/2005 - 8/31/2007
Laura Lurati University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Gennady Lyubeznik University of Minnesota Twin Cities 9/1/2006 - 6/30/2007
Dinesh Manocha University of North Carolina 5/28/2007 - 5/29/2007
Hannah Markwig University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Thomas Markwig Universität Kaiserslautern 9/1/2006 - 6/30/2007
Kurt Mehlhorn Max-Planck-Institut für Informatik 5/28/2007 - 6/1/2007
Richard B. Moeckel University of Minnesota Twin Cities 9/1/2006 - 6/30/2007
Brian Moore Johann Radon Institute for Computational and Applied Mathematics 5/28/2007 - 6/2/2007
Bernard Mourrain Institut National de Recherche en Informatique Automatique (INRIA) 5/27/2007 - 6/3/2007
Uwe Nagel University of Kentucky 9/1/2006 - 6/1/2007
Jiawang Nie University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Michael E. O'Sullivan San Diego State University 4/12/2007 - 5/11/2007
Laxmi Parida IBM Thomas J. Watson Research Center 5/3/2007 - 5/6/2007
Dmitrii Pasechnik Nanyang Technological University 5/14/2007 - 6/14/2007
Martin Peternell Technische Universität Wien 5/28/2007 - 6/3/2007
Jorg Peters University of Florida 5/28/2007 - 6/2/2007
Ragni Piene University of Oslo 5/28/2007 - 6/2/2007
Bharath Rangarajan University of Minnesota Twin Cities 5/29/2007 - 6/2/2007
Tomas Recio University of Cantabria 5/28/2007 - 6/3/2007
Victor Reiner University of Minnesota Twin Cities 9/1/2006 - 6/30/2007
Joel Roberts University of Minnesota Twin Cities 9/1/2006 - 6/30/2007
Marie Rognes University of Oslo 1/10/2007 - 6/30/2007
J. Maurice Rojas Texas A & M University 4/11/2007 - 6/3/2007
Bjarke Hammersholt Roune Aarhus University 9/12/2006 - 6/30/2007
David Rusin Northern Illinois University 5/27/2007 - 6/2/2007
Arnd Scheel University of Minnesota Twin Cities 7/15/2004 - 8/31/2007
Chehrzad Shakiban University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Milind Sohoni Indian Institute of Technology 4/13/2007 - 5/18/2007
Frank Sottile Texas A & M University 2/26/2007 - 6/30/2007
Steven Sperber University of Minnesota Twin Cities 9/1/2006 - 6/30/2007
Reinhard Steffens Johann Wolfgang Goethe-Universität Frankfurt 5/28/2007 - 6/3/2007
Ileana Streinu Smith College 5/28/2007 - 6/2/2007
Rebecca Swanson Indiana University 5/3/2007 - 5/16/2007
Agnes Szanto North Carolina State University 5/28/2007 - 6/1/2007
Thorsten Theobald Johann Wolfgang Goethe-Universität Frankfurt 5/28/2007 - 6/2/2007
Louis Theran University of Massachusetts 5/28/2007 - 6/2/2007
Carl Toews University of Minnesota Twin Cities 9/1/2005 - 8/31/2007
Elias P. Tsigaridas Institut National de Recherche en Informatique Automatique (INRIA) 5/26/2007 - 6/3/2007
John Voight University of Minnesota Twin Cities 8/15/2006 - 8/31/2007
Wenping Wang University of Hong Kong 5/28/2007 - 6/2/2007
Nicola Wolpert Stuttgart University of Applied Sciences 5/27/2007 - 6/3/2007
William Wood Corning 5/28/2007 - 6/3/2007
Fei Yang University of Minnesota Twin Cities 5/29/2007 - 6/2/2007
Josephine Yu University of California 1/9/2007 - 6/30/2007
Hongchao Zhang University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Ming Zhang University of Texas 5/31/2007 - 6/3/2007
Severinas Zube Vilnius State University 5/28/2007 - 6/3/2007
Legend: Postdoc or Industrial Postdoc Long-term Visitor

IMA Affiliates:
3M, Boeing, Carnegie-Mellon University, Corning, ExxonMobil, Ford, General Electric, General Motors, Georgia Institute of Technology, Honeywell, IBM, Indiana University, Iowa State University, Johnson & Johnson, Kent State University, Lawrence Livermore National Laboratory, Lockheed Martin, Los Alamos National Laboratory, Medtronic, Michigan State University, Michigan Technological University, Mississippi State University, Motorola, Northern Illinois University, Ohio State University, Pennsylvania State University, Purdue University, Rice University, Rutgers University, Sandia National Laboratories, Schlumberger-Doll, Schlumberger-Doll Research, Seoul National University, Siemens, Telcordia, Texas A & M University, University of Chicago, University of Cincinnati, University of Delaware, University of Houston, University of Illinois at Urbana-Champaign, University of Iowa, University of Kentucky, University of Maryland, University of Michigan, University of Minnesota, University of Notre Dame, University of Pittsburgh, University of Texas, University of Wisconsin, University of Wyoming, US Air Force Research Laboratory, Wayne State University, Worcester Polytechnic Institute