Computation of Adjoints for Surfaces

GENERAL INFORMATION

Project Data

Sponsor:

Austrian Science Fund (FWF)

Duration:

January 1998 - April 2000

Project Leader:

Josef Schicho

Project Members:

Gábor Bodnár

Wolfgang Stöcher

Former Members:

Werner Heiss

Bogdan Matasaru

Email address:

adjoints@risc.uni-linz.ac.at

Examples

Figure 1: A surface with a singular line.

Figure 2: A 1-adjoint.

Short Introduction

The method of adjoints is a powerful tool for performing various tasks in constructive, algebraic geometry, most notably the parametrization of algebraic curves (see the CASA homepage) and the parametrization of algebraic surfaces. In the surface case, the problem of computing adjoints is still very difficult. It is closely related to the problem of resolution of singularities.

Goal

The goal is to devise an efficient algorithm for the following problem.

Input:: A surface in 3-space, given implicitly.
Two integers n, m.
Output:: The `m-adjoints of degree n' of the surface.

An `m-adjoint of degree n' of a surface is a polynomial of degree n that vanishes with a certain order (depending on m) on the singularities of the surface. For example, look at the surface in figure 1. It has a singular line L. The polynomial given by G in figure 2 is a 1-adjoint of degree 1.

The set of all m-adjoints of degree n forms a vector-space. The output of the algorithm should be a basis.

Relevance

Computation of adjoints is important because it is currently the only way to solve the parameterization problem, which is essential to compute NURBS-representations, which have numerous applications in CAD/CAM, such as

reliable surface plotting and display,
motion display (computing transformations),
computing cutter offset surfaces,
computing curvatures for shading and colouring,
and many others.

Moreover, the computation of adjoints is important because it can be applied to solve classification problems for surfaces.

State of The Art

In the curve case, adjoints are well understood theoretically, and there are several algorithms for the computation, some of them efficient.

In the surface case, adjoints are also well understood theoretically, but we still cannot compute them efficiently. Currently, there is only one algorithm (by Schicho, one of the proposers), and this one is too slow.

A problem closely related to the computation of adjoints is the resolution of singularities. There are several approaches for this problem, but no complexity bounds are known for any of the existing methods.

SUBPROJECTS

Resolution of Singularities

The problem of resolution of singularities for hypersurfaces, in brief, is to find a proper birational morphism from some nonsingular algebraic set to a given hypersurface.

In this subproject, we study the problems of algorithmic resolution of singularities. We developed a software package (desing), which resolves singularities of hypersurfaces in characteristic zero, relying on the stratifying function of Villamayor./

Surface Parametrization

We are given an algebraic surface by its equation, and we want to find its parametrization in terms of rational functions in two parameters, if such a representation exists.

In this subproject, we implement J. Schicho's results on surface parametrization (see the publication list), while doing research in related open problems (e.g. real parametrization of real algebraic surfaces).

ACHIEVEMENTS / ACTIVITIES

List of Publications

J. Schicho^*: Inversion of rational maps with Gröbner bases. In B. Buchberger and F. Winkler editors, Gröbner bases and applications. Cambridge Univ. Press 1998.

J. Schicho: Rational parametrization of surfaces. J. Symb. Comp., 26 (1): 1-30, July 1998.

J. Schicho^*: Rational parametrization of real algebraic surfaces. In ISSAC-98, pages 302-308. ACM Press, 1998.

J. Schicho: A degree bound for the parameterization of a rational surface. J. Pure Appl. Alg., 1999 to appear.

G. Bodnár and J. Schicho: A computer program for the resolution of singularities. In Resolution of Singularities. ed. H. Hauser, Birkhäuser, 2000, to appear.

G. Bodnár and J. Schicho: Automated resolution of singularities for hypersurfaces. J. Symb. Comp., 2000 to appear.

G. Bodnár and J. Schicho^*: An improved algorithm for the resolution of singularities. In Proceedings of ISSAC 2000, ACM Press, 2000, to appear.

Techinical Reports

B. Matasaru and J. Schicho: The complexity analysis for an algorithm to compute adjoints for curves due to Jeremy Teitelbaum. Technical Report 98-21, RISC-Linz, Univ. Linz, A-4040 Linz, 1998.

J. Schicho: A direct method for polynomial parametrization of curves. Technical Report 99-02, RISC-Linz, Univ. Linz, A-4040 Linz, 1999.

J. Schicho: The parametrization problem for algebraic surfaces. Technical Report 99-22, RISC-Linz, Univ. Linz, A-4040 Linz, 1999.

J. Schicho^*: Embedded desingularization of hypersurfaces after Villamayor, Technical Report 97-28, RISC-Linz, Univ. Linz, A-4040 Linz, 1997.

G. Bodnár and J. Schicho: Improvements of the algorithm for resolution of singularities, Technical Report 00-03, RISC-Linz, Univ. Linz, A-4040 Linz, 2000.

Submitted Papers

J. Schicho^*: Proper parametrization of real algebraic surfaces. Technical Report 99-19, RISC-Linz, Univ. Linz, A-4040 Linz, 1999.

^* Assigned to a different project, but with content closely related to this project.

Conference Talks

G. Bodnár and J. Schicho: On algorithmic desingularization of hypersurfaces, 1998 talk at IMACS-ACA '98, Prague.

J. Schicho: Rational parametrization of real algebraic surfaces, 1998 invited talk at Univ. of Cantabria, Spain.

J. Schicho: A degree bound for the parametrization of a rational surface, 1996 invited talk at Univ. of Complutense, Spain.

J. Schicho: Rational parametrization of real algebraic surfaces, 1998 talk at ISSAC-98, Rostock.

J. Schicho: Automated resolution of singularities, 1999 invited talk ar Univ. Autonoma Madrid.

J. Schicho: Proper parametrization of real algebraic surfaces, 1999 invited talk at Univ. of Wien.

J. Schicho: Proper parametrization of real algebraic surfaces, 1999 talk at IMACS-ACA '99, Madrid.

J. Schicho: The parametrization problem of algebraic surfaces, 1999 talk at IMACS-ACA '99, Madrid.

J. Schicho and W. Stöcher: Automated parametrization of algebraic surfaces, 1999 poster at GD '99, Albuquerque.

G. Bodnár and J. Schicho: An algorithm for resolution of singularities, 1999 poster at ECCAD '99, NCSU, Raleigh.

Software

G. Bodnár and J. Schicho: Desing. A Maple V package for resolution of singularities of hypersurfaces in characteristic zero. (1998-99)

Project Seminar

J. Schicho: Applications of Sheaf Theory (1998-), Proceedings

Project Documents

H. Hong and J. Schicho: Proposal

J. Schicho: Annual report 1998

Resolution of singularities (subproject)

Surface parametrization (subproject)

Austrian Science Fund (FWF)

Working Week on Resolution of Singularities

CASA A computer algebra software for constructive algebraic geometry.

Mgfun home page.

Maintained by: The Adjoints Project
Last Modification: June 23, 2000

[Up] [RISC-Linz] [University] [Search]