User Tools

Site Tools


public:events:specsem2013:workshop3

List of abstracts

Please add/update the abstract of your talk by loging in and then clicking on your name in the list of names in the upper right, and then on the Edit button below your name.

If you need LaTeX do it as follows: <latex>\frac{a}{b}</latex>

John Abbott

Evaluation of Polynomials

  • Duration: 20 minutes

We present some algorithms for evaluating a polynomial at a point. We consider certain special cases such as polynomials whose coefficients lie in a small set, and univariate polynomials with integer coefficients.

Carlos D'Andrea

Implicitization of rational plane varieties via moving surfaces

  • Duration: 40 minutes

In the mid 90's several methods for implicitization of rational parametrizations by using moving planes or quadrics were explored in the Computer Aided Geometric Design Community. The analysis of the validity of these methods engaged a whole community in Commutative and Computational Algebra, and several results have been obtained so far. Still, a lot of research is being done currently around this topic. In this survey we will present these methods and show how their precise mathematical formulation, as well as current results.

Goulnara Arzhantseva

Amenability and Coarse monsters

  • Coauthors: Erik Guentner (Hawaii), Jan Spakula (Southampton), Romain Tessera (Orsay).
  • Duration: 40 minutes

The concept of coarse embedding was introduced by Gromov in 1993. It plays a crucial role in the study of large-scale geometry of groups and the Novikov higher signature conjecture. Coarse amenability, also known as Guoliang Yu's property A, is a weak amenability-type condition that is satisfied by many known metric spaces. It implies the existence of a coarse embedding into a Hilbert space.

In this talk, we discuss the interplay between infinite expander graphs, coarse amenability, and coarse embeddings. We present several ``monster'' constructions in the setting of metric spaces of bounded geometry.

This research was partially supported by my ERC grant ANALYTIC no. 259527.

Felix Breuer

The Many Uses of Polyhedral Geometry in Combinatorics and Beyond

  • Coauthors: Zafeirakis Zafeirakopoulos
  • Duration: 40 minutes

Many combinatorial problems can be viewed through the lens of polyhedral geometry. This perspective is surprisingly useful, not only in applied areas such as operations research, but also in many areas of “pure” mathematics.

The enumerative part of the theory of integer points in polyhedra is called Ehrhart Theory. In this talk, I will present the highlights of Ehrhart theory - Ehrhart-Macdonald reciprocity, Brion decompositions, Barvinok’s short rational function representations - and illustrate them with several combinatorial applications, including recent results from my own research. This will lead up to a new algorithm for solving linear Diophantine systems, which brings together ideas from MacMahon’s partition analysis with polyhedral methods.

This talk is introductory. While I will present some recent results, the goal of this talk is to give an overview of the field that is accessible to a general mathematical audience.

Madalina Erascu

Synthesis of Optimal Numerical Algorithms by Real Quantifier Elimination (Case Study: Square Root Computation)

  • Coauthors: Hoon Hong
  • Duration: 20 minutes

Numerous problems in mathematics, science and engineering can be reduced to real quantifier elimination (quantifier elimination over real closed fields). Around 1930, Alfred Tarski showed that real quantifier elimination can be carried out algorithmically. In 1975, George Collins provided a dramatically more efficient algorithm. Since then, there has been intensive research to make further improvement of efficiency for a certain important class of formulas (inputs). In our research, we consider formulas arising in the synthesis of optimal numerical algorithms. In this talk, we present a case study on the square root problem: given the real number x and the error bound eps, find a real interval such that it contains sqrt(x) and its width is less than eps. As usual, we begin by fixing an algorithm schema, namely, iterative refining: the algorithm starts with an initial interval and repeatedly updates it by applying a refinement function, say R, on it until it becomes narrow enough. Then the synthesis amounts to finding a refinement function R that ensures that the algorithm is correct (loop invariant), terminating (contraction), and optimal. All these can be formulated as quantifier elimination over the real numbers. Hence, in principle, they can be all carried out automatically. However the computational requirement is so huge, making the automatic synthesis practically impossible with the current general quantifier elimination software. Hence, we did some hand derivations and were able to synthesize semi-automatically optimal algorithms under suitable assumptions. We hope that the ideas behind the hand derivations could be eventually turned into an algorithm.

Jean-Charles Faugere (INRIA/UPMC - LIP6)

Recent progress on computing Gröbner bases: theory and practice

Computing Gröbner bases is one of the most efficient method to solve polynomial systems over finite fields. Until recently, the change of the ordering of a Gröbner basis from DRL to LEX was the bottleneck of the whole solving process. To overcome this issue we have proposed several efficient algorithms. First, the sparse-FGLM (with C. Mou) can take advantage of the sparsity of multiplication matrices in the classical FGLM algorithm to decrease the theoretical and practical complexity. Hence, we have now a fast implementation that is able to handle ideals of degree over 300000. Second, the fast-FGLM algorithm (with P. Gaudry, L. Huot and G. Renault) can reduce the change of the ordering of a Gröbner basis to few matrix multiplications. As a consequence, the theoretical complexity can be furthermore reduced to O(D^w) where w<2.3727 is the exponent in the complexity of multiplying two dense matrices and D is the number of solutions. Surprisingly this ideas can also useful to reduce the practical computation time. The new algorithms have been successfully applied to various problems such as the Discrete Logarithm Problems for Edwards elliptic curves defined over a non prime finite field GF(q^n).

Joachim von zur Gathen

Survey on Counting Special Types of Polynomials

  • Coauthors: Raoul Blankertz, Mark Giesbrecht, Alfredo Viola, and Konstantin Ziegler
  • Duration: 40 minutes

Most integers are composite and most univariate polynomials over a finite field are reducible. The Prime Number Theorem and a classical result of Gauss count them approximately and exactly.

In two or more variables, the situation changes dramatically. Most multivariate polynomials are irreducible. We present counting methods for some special classes of multivariate polynomials over a finite field, namely the the reducible ones, the s-powerful ones (divisible by the s-th power of a nonconstant polynomial), and the relatively irreducible ones (irreducible but reducible over an extension field). They yield exact formulas and approximations with relative errors that essentially decrease exponentially in the input size.

Furthermore, a polynomial f (univariate or multivariate) is decomposable if f = g ° h for some nonlinear polynomials g and h. It is intuitively clear that the decomposable polynomials form a small minority among all polynomials. The tame case, where the characteristic p of Fq does not divide n = deg f, is fairly well-understood, and we obtain closely matching upper and lower bounds on the number of decomposable polynomials. In the opposite wild case, the bounds are less satisfactory. The crux of the matter is to count the number of collisions, where different (g, h) yield the same f. We present a classification of all collisions at degree n = p².

Shuhong Gao

Recent progress on computing Groebner bases

  • Coauthors: Frank Volny IV (National Security Agency) and Mingsheng Wang (Chinese Academy of Sciences)
  • Duration; 40 minutes

Buchberger (1965) gave the first algorithm for computing Groebner bases and introduced some simple criterions for detecting useless S-pairs. Faugere (2002) presented the F5 algorithm which is significantly much faster than Buchberger's algorithm and can detect all useless S-pairs for regular sequences of homogeneous polynomials. In recent years, there has been extensive effort trying to simply F5 and to give a rigorous mathematical foundation for F5. In this talk, we present a simple criterion for strong Groebner bases that contain Groebner bases for both ideals and the related syzygy modules. This criterion can detect all useless J-pairs (without performing any reduction) for any sequence of polynomials, thus yielding an efficient algorithm for computing Groebner bases and a simple proof of finite termination of the algorithm.

Mark Giesbrecht

Algorithms and statistics for additive polynomials

  • Coauthors: Joachim von zur Gathen, Konstantin Ziegler
  • Duration; 40 minutes

The additive or linearized polynomials were introduced by Ore in 1933 as an analogy over finite fields to his theory of difference and difference equations over function fields. The additive polynomials over a finite field \mathbb{F}_q, where $q=p^e$ for some prime $p$, are those of the form

$$
f=\sum_{0\leq i\leq \mu} f_i x^{r^i}\in\mathbb{F}[x],
$$

for some $r=p^m$. They form a non-commutative left-euclidean principal ideal domain under the usual addition and functional composition, and possess a rich structure in both their decomposition structures and root geometries. Additive polynomials have been employed in number theory and algebraic geometry, and applied to constructing error-correcting codes and cryptographic protocols. In this talk we will present fast algorithms for decomposing and factoring additive polynomials, and also for counting the number of decompositions with particular degree sequences.

Algebraically, we show how to reduce the problem of decomposing additive polynomials to decomposing a related associative algebra, the eigenring. We give computationally efficient versions of the Jördan-Holder and Krull-Schmidt theorems in this context to describe all possible factorization. Geometrically, we show how to compute a representation of the Frobenius operator on the space of roots, and show how its Jordan form can be used to count the number of decompositions. We also describe an inverse theory, from which we can construct and count the number of additive polynomials with specified factorization patterns.

Willem A. De Graaf

Orbit closures of linear algebraic groups

  • Duration: 40 minutes

Let an algebraic group be given, acting on a vector space. We consider the problem of deciding whether a given element of the vector space lies in the closure of the orbit of another given element. We describe three methods for dealing with this problem that have appeared in the literature. The first one, proposed by Popov, is a straightforward reduction to elimination using Groebner bases. The second method, also due to Popov, is based on the effective Nullstellensatz. Both these methods use an open subset of the group, isomorphic to an “easy” affine algebraic set. The third method, developed by de Graaf, Vinberg and Yakimova, is specific for reductive groups that are constructed as so-called θ-groups. We illustrate the methods by examples. We also comment on the practical usefulness of them.

Georg Grasegger

Radical solutions of algebraic differential equations

  • Duration; 20 minutes

We consider autonomous first order algebraic differential equations (AODEs), F(y,y')=0, with the usual derivative and we are interested in radical solutions. Using rational parametrizations of the algebraic curve defined by the polynomial F, Feng and Gao give a full decision algorithm for finding rational solutions. Presenting a method which generalizes the rational algorithm we are able to determine radical solution functions. To do so we extend the class of parametrizations to radical ones.

This research was supported by the Austrian Science Fund (FWF): W1214-N15, project DK11

Herwig Hauser

Platonic Stars: Where Invariant Theory meets Singularities.

  • Duration; 40 minutes

While astronomic stars are actually balls, we perceive them with cusps and spikes, due to the reception of the light rays by the retina. Mathematicians are then led to ask whether such anthropogenic stars can be defined as the zerosets of algebraic equations.

For starshaped plane curves, the answer is classical and given by cycloids, the most prominent example being the astroide with equation x^{2/3} + y^{2/3}=1. For surfaces, the answer is more intricate. Two requirements seem to be natural: The star should have the symmetry group of a platonic solid, and be a compact real-algebraic surface with only isolated singularities in the cuspidal points.

In the talk, we will present the mathematical ingredients from invariant and singularity theory which are necessary to give a complete construction of the appropriate equations. We will also raise and discuss a couple of questions about finding parametrizations and axiomatic descriptions of these shapes.

Hoon Hong

Root Separation Bound

  • Coauthors: Aaron Herman
  • Duration; 40 minutes

Let f be a square-free polynomial. The root separation of f is the minimum of the pair-wise distances between the complex roots of f. Finding a lower bound on the root separation is a fundamental problem, arising in numerous disciplines. Due to its importance, there has been extensive research on this problem, resulting in various bounds. In this talk, we present another bound, which is “nicer” than the previous bounds in that (1) It is bigger (hence better) than the previous bounds. (2) It is invariant under the translation of the roots, unlike the previous bounds. (3) It is covariant under the scaling of the roots, unlike the previous bounds.

Jorge Jimenez-Urroz

Irreducibility and the distribution of some exponential

  • Duration; 40 minutes

The talk is about irreducibility of P(x)-P(y)+r for any polynomial P and non zero r. This gives applications to bounds on exponential sums, and the fractal behaviour of the Riemann function. We will explain these concepts also.

Antoine Joux

Discrete logarithms: Recent progress (and open problems)

  • Coauthors: Cécile Pierrot (second part)
  • Duration: 40 minutes

In this talk, we present several recent improvements on the computation of discrete logarithms in finite fields.

The first part presents a quasi-polynomial algorithm for computing discrete logarithms in fields of small characteristic. The main ingredient in a new method for generating multiplicative relations with a “systematic side” by composing the polynomial (X^q-X) with homographies.

The second part of the talk shows that the SNFS (special number field sieve) is not only an option for prime fields but can be generalized to extension fields, when the characteristic has a “sparse” expression. As a result, we obtain a variant of NFS with reduced complexity. In particular, this can be applied to some pairing-based constructions.

Erich Kaltofen

Multivariate Sparse Interpolation and Error Correction Coding

  • Coauthors: Matthew Comer (NCSU), Clement Pernet (Univ. Grenoble), and Zhengfeng Yang (ECNU, Shanghai).
  • Duration; 40 minutes

Error-correcting decoding is generalized to multivariate sparse polynomial and rational function interpolation from evaluations that can be numerically inaccurate and where several evaluations can have severe errors (outliers).

Our univariate solution for numerical Prony-Blahut/Giesbrecht-Labahn-Lee sparse interpolation can identify and remove outliers by a voting scheme.

Our multivariate polynomial and rational function interpolation algorithm combines Zippel's symbolic sparse polynomial interpolation technique [Ph.D. Thesis MIT 1979] with the numeric algorithm by Kaltofen, Yang, and Zhi [Proc. SNC 2007], and removes outliers (“cleans up data”) by techniques from the Berlekamp/Welch decoder for Reed-Solomon codes, that even when the error rate in nearly 10%.

Manuel Kauers

Ore Polynomials in Sage

  • Coauthors: Maximilian Jaroschek, Fredrik Johansson
  • Duration: 40 minutes

We present a Sage implementation of Ore algebras. The main features for the most common instances include basic arithmetic and actions; gcrd and lclm; D-finite closure properties; natural transformations between related algebras; guessing; desingularization; solvers for polynomials, rational functions and (generalized) power series. This paper is a tutorial on how to use the package.

Christian Krattenthaler

A (semi-) automatic method for the determination of differentially algebraic integer sequences modulo powers of 2 and 3

  • Coauthors: Manuel Kauers, Thomas Müller
  • Duration; 40 minutes

I shall describe a generating function approach to determine the congruence behaviour modulo powers of $2$ and $3$ of integer sequences whose generating function is differentially algebraic (i.e., satisfies a polynomial differential equation). This approach can be fully automatised (if it applies). It applies to many combinatorial sequences, such as, for example, Catalan numbers, Motzkin numbers, Schröder numbers, trinomial coefficients, Eulerian numbers, etc. The method leads to some open questions on the minimal degree of a polynomial satisfied by certain power series which form the base for the approach.

Zijia Li

RCCR Linkages

  • Coauthors: Josef Schicho
  • Duration; 20 minutes

This talk is divided into two parts. First, I will introduce the relation between linkages and algebra (DH). Second, I will introduce a theory called “bond theory”. This theory gives a basic classification of linkages. But this classification is implicit. You can not generate each type just by its bond structure. In my talk, I will mainly focus on bond theory with prismatic joints. Finally, I show a classification of the linkage in RCCR type.

Niels Lubbes

Elliptic translational surfaces with families of circles

  • Duration; 20 minutes

http://www.risc.jku.at/people/nlubbes/circle/circles.html http://arxiv.org/abs/1306.1917

The sphere in 3-space has an infinite number of circles through any closed point. The torus has 4 circles through any closed point. Two of these circles are known as Villarceau circles. We define a 'celestial' to be a real surface with at least 2 real circles through a generic closed point. Equivalently, a celestial is a surface with at least 2 families of real circles.

In 1980 Blum conjectured that a real surface has either at most 6 families of circles or an infinite number. For compact surfaces this conjecture has been proven by Takeuchi in 1987 using topological methods. In 2001 Schicho classified complex surfaces with at least 2 families of conics. This result together with Moebius geometry led to a classification of celestials in 3-space.

We recall that a translation is an isometry where every point moves with the same distance. In this talk we consider celestials in 3-space that are obtained from translating a circle along a circle, in either Euclidean or elliptic space. This is a natural extension of classical work by William Kingdon Clifford and Felix Klein on the Clifford torus.

Rimas Krasauskas, Helmut Pottmann and Mikhail Skopenkov conjectured, that celestials in 3-space of Moebius degree 8 are Moebius equivalent to an Euclidean or elliptic translational celestial. This conjecture is true if its Moebius model has a family of great circles. Moreover, its real singular locus consist of a great circle. As a corollary we obtain a classically flavored theorem in elliptic geometry: if we translate a line along a circle but not along a line then exactly 2 translated lines will coincide.

We will end the talk with open problems.

Peter Paule

Computer Algebra, Ramanujan Congruences, and Polynomials

  • Coauthor: Cristian-Silviu Radu
  • Duration; 40 minutes

Abstract: The number of partitions of 4 is p(4)=5, namely: 4, 3+1, 2+2, 2+1+1, and 1+1+1+1. Ramanujan observed that p(5n+4) is divisible by 5 for all non-negative integers n. More generally, Ramanujan discovered similar congruences modulo 7 and 11, and also for all powers of these primes. The talk describes new algorithmic developments (by Cristian-Silviu Radu and also in joint work with Radu) in the theory of modular forms that give rise to a new unified proving frame for these celebrated families of partition congruences. A key role is played by certain bivariate monic polynomials whose existence is due to a variant of a classical fact from Riemann surfaces.

Ludovic Perret

Algebraic Techniques in Code-Based Cryptography

  • Coauthors: Jean-Charles Faugère, Ayoub Otmani, Jean-Pierre Tillich
  • Duration; 20 minutes

The purpose of this talk is first to briefly explain how the key-recovery problem in McEliece's cryptosystem reduces to the problem of solving an algebraic system of equations which is highly structured. We then show that this approach can be used to solve the so-called the Goppa Code Distinguishing (GD) problem. This is the problem of distinguishing the public matrix in the McEliece cryptosystem from a random matrix. It is widely believed that this problem is computationally hard as proved by the increasing number of papers using this hardness assumption. One can consider that disproving/mitigating this hardness assumption is a breakthrough in code-based cryptography. We present an efficient distinguisher for alternant and Goppa codes over binary/non binary fields for certain parameters. We exploit a defect of rank in the (linear) system obtained by linearizing the key-recovery algebraic system. It turns out that our distinguisher is also highly discriminant. Indeed, we are able to precisely quantify the defect of rank for “generic“ binary and non-binary random, alternant and Goppa codes. We have verified these formulas with practical experiments, and a theoretical explanation for such defect of rank is also provided.

Adrien Poteaux

Towards fast Puiseux series computation

  • Coauthors: Marc Rybowicz
  • Duration: 20 minutes

Singularities provide a lot of informations on curves, but are usually tough to deal with. One way to do so is to compute Puiseux expansions via the well known Newton-Puiseux algorithm. The later solves the problem, but not in an efficient way (best known arithmetic complexity is more than quadratic, and bit complexity is even worse due mainly to coefficients growth). We will briefly present the current state of our work towards a fast algorithm for Puiseux series computation. Besides the symbolic-numeric strategy from our previous work, we will also provide the ideas of a new algorithm that improves previous complexity bounds.

Zoltan Kovacs and Bernard Parisse

Giac and GeoGebra --- improved Groebner basis computations

  • Duration: 20 minutes

GeoGebra is an open source mathematics education software being used in thousands of schools worldwide. It already supports equation system solving, locus equation computation and automatic geometry theorem proving by using an embedded or outsourced CAS. GeoGebra recently changed its embedded CAS from Reduce to Giac because it fits better the educational use. Also careful benchmarking of open source Groebner basis implementations showed that Giac is also fast in algebraic computations, therefore it allows heavy Groebner basis calculations even in a web browser via Javascript.

Groebner basis on Q for revlex ordering implementation in Giac is a modular algorithm (E. Arnold). Each Z/pZ computation is done via Buchberger algorithm using F4 linear algebra technics and “remake” speedups, they might be run in parallel for large examples. The output can be probabilistic or certified (which is much slower). Experimentation shows that the probabilistic version is faster than other open-source implementations, and about 3 times slower than the Magma implementation on one processor, it also requires less memory for big examples like cyclic9.

Ragni Piene

Polar varieties revisited

Duration: 40 minutes

Polar varieties and polar classes have played an important role in the study and classification of projective varieties. In particular they were used to give geometric definitions of Todd classes and Chern classes. Their local counterpart was used in singularity theory. More recently they have been studied and generalized also in the context of real projective and affine geometry, with applications to finding points on real components, to compute Euclidean distance degrees, to caustics by reflection.

Hamid Rahkooy

Determining the elimination ideal of a bivariate ideal from its multiplicity structure

  • Coauthors: Matteo Gallet, Angelos Mantzaflaris, Zafeirakis Zafeirakopoulos
  • Duration: 15 minutes

Our work takes the cue from the following observation: given a zero-dimensional bivariate ideal  I = \langle f_1, f_2 \rangle \subseteq
C[x,y] , we can think of it as the ideal of the intersection of two affine curves  C_1 and  C_2 ; if we suppose that all the  \deg f \deg g intersections { P_j } of the two curves (which a priori might lie on the line at infinity) are actually given by affine points, then the monic generator  g of the elimination ideal  I' = I \cap C[y] is of the form  g = \prod (y - \beta_i)^{m_i} . Now, the numbers $m_i$ are in general different from the intersection multiplicity of C_1 and C_2 at the corresponding point P_i.

By inspecting the geometric situation, we realize that these differences appear when the two curves meet with multiplicity (e.g. with a tangent parallel to the x-axis), or when some of the P_i's are horizontally aligned. To explain this phenomenon, we look at the multiplicity structure of the points of intersection.

Using the description of the multiplicity structure in terms of local differential operators and the properties of the dual space, we relate the multiplicity of the factors of g to geometric information at the intersection points of C_1 and C_2.

Kristian Ranestad

Symmetric Tensor Decompositions

Duration: 40 minutes

Geometry and algebra of decompositions of homogeneous polynomials as sums of powers of linear forms. A survey of old and more recent results on various notions of rank and the variety of powersums of a given form.

Lajos Rónyai

Splitting full matrix algebras over small number fields

  • Coauthors: Gábor Ivanyos, Ádám Lelkes, Josef Schicho
  • Duration; 40 minutes

Let K be a number field of degree d and discriminant D over the rationals. Let A be an input associative algebra over K such that A is isomorphic to the algebra M_n(K) of all n by n matrices. Suppose that d, n and D are bounded. Then an isomorphism of A with M_n(K) can be constructed by a polynomial time ff-algorithm. (An ff-algorithm is a deterministic procedure which is allowed to call oracles for factoring integers and factoring univariate polynomials over finite fields.)

In addition to computing with representations, the algorithm can be applied to parametrization problems of algebraic geometry, and to computations with n-Selmer groups of elliptic curves.

The method leads to a polynomial time ff-algorithm to compute isomorphisms of central simple algebras of bounded degree over K.

Carsten Schneider

Fast Algorithms for Refined Parameterized Telescoping in Difference Fields

  • Duration: 40 minutes

Parameterized telescoping (including telescoping and creative telescoping) and refined versions of it play a central role in the research area of symbolic summation. In 1981 Karr introduced \Pi\Sigma-fields, a general class of difference fields, that enables one to consider this problem for indefinite nested sums and products covering as special cases, e.g., the (q-)hypergeometric case and their mixed versions. This survey article presents the available algorithms in the framework of \Pi\Sigma-extensions and elaborates new results concerning efficiency

J. Rafael Sendra

Global and Approximate Parametrization of Algebraic Curves

  • Duration; 20 minutes

In some pratical applications in computer aided design, computer graphics, geometric modeling, etc, rational curves are used in their manipulations. However, it usually happens that the input curve, even though is known (theoretically) to have genus 0, because of the imprecisions of computations, measures, etc, turns to be of positive genus. Therefore the exact symbolic approaches cannot be applied anymore. In this situation, the use of alternative approaches, as approximate techniques, is unavoidable. Some approximate techniques, as ours, provide approximate global rational parameterizations, if they exist, others generate piecewise rational parametrizations, in both cases, under a given precision.

In this talk we plan to review some of our new achievements in the frame of this problem, for the case of plane and space algebraic curves.

This work has been done under the research project MTM2011-25816-C02-01 (Spanish “Ministerio de Economía y Competitividad”)

David Sevilla

Coverings of affine parametric surfaces with no projective base points

  • Coauthors: J. Rafael Sendra, Carlos Villarino
  • Duration; 20 minutes

I will give some basic notions on surface parametrizations and explain how one can cover an affine algebraic surface when a (non-surjective) parametrization without projective base points is given.

This work has been partially supported by the research project MTM2011-25816-C02-01 (Spanish “Ministerio de Economía y Competitividad”)

Laura Torrente

Almost vanishing polynomials and an application to Hough transforms

  • Coauthors: Mauro C. Beltrametti
  • Duration; 20 minutes

In this talk we consider the problem of deciding whether or not an affine hypersurface of equation f=0, where f=f(x_1,…,x_n) is a polynomial in R[x_1,…,x_n], crosses a bounded region T of the real affine space A^n. We perform a local study of the problem, and provide both necessary and sufficient numerical conditions to answer the question. Our conditions are based on the evaluation of f at a point p in T, and derive from the analysis of the differential geometric properties of the hypersurface z=f(x_1,…,x_n) at p. We also present an application of our results to Hough transforms, a pattern recognition technique for the automated recognition of curves in images.

Carlos Villarino

Ultraquadrics and its application to the reparametrization of rational complex surfaces.

  • Duration; 20 minutes

Given a rational variety V, of dimension m, by means of a parametrization with m parameters t1,…,tm (and coefficients in an algebraic extension K(a)), it is natural to ask for the possibility of reparameterizing it over a field as simple as possible (i.e. the problem of the K-algebraic optimality for rational varieties). The ultraquadrics are rational varieties generated by the authomorphisms of the field k(a)(t1,…,tm), that can help to solve the problem of reparametrizing V over K, when it is possible. However, the complexity of the general case and the practical interest in applications of the real-complex case (i.e when K=R and k(a)=C) for rational surfaces, motivates the analysis and study in this case.

In this talk we plan to review some of our new achievements in the frame of this problem. More precisely, we present algorithms to decide whether a given parametrization of a rational ruled surface, or a rational swung surface (that includes rational surfaces of revolution) with coefficients in K(i) (K is a computable subfield of the real numbers, for instance Q), can be reparematrized over K.

This work has been done under the research project MTM2011-25816-C02-01 (Spanish “Ministerio de Economía y Competitividad”).

Franz Winkler

Symbolic solutions of algebraic differential equations

  • Duration: 40 minutes

Consider an algebraic ordinary differential equation (AODE) of the form F (x, y, y′) = 0, where F is an irreducible tri-variate polynomial, and y′ = dx . The polynomial F defines an algebraic surface, which we assume to admit a rational parametrization. Based on such a parametrization we can generically determine the existence of a rational general solution, and, in the positive case, also compute one. This method depends crucially on curve and surface parametrization and the determination of rational invariant algebraic curves. We describe an algorithm for computing a rational general solution, if it exists. Further research is directed towards a classification of AODEs w.r.t. groups of transformations (affine, birational) preserving rational solvability; higher order differential equations; and other types of parametrizations.

References

  1. R. Feng, X.-S. Gao, A polynomial time algorithm for finding rational general solutions of first order autonomous ODEs, J. Symbolic Computation, 41, 739–762 (2006).
  2. Y. Huang, L.X.C. Ngô, F. Winkler, Rational general solutions of higher order algebraic ODEs, to appear in J. Systems Science and Complexity (2012).
  3. E. Hubert, The general solution of an ordinary differential equation, Proc. ISSAC’1996, 189–195 (1996).
  4. L.X.C. Ngô, F. Winkler, Rational general solutions of first order non-autonomous parametrizable ODEs, J. Symbolic Computation, 45(12), 1426–1441 (2010).
  5. L.X.C. Ngô, F. Winkler, Rational general solutions of planar rational systems of autonomous ODEs, J. Symbolic Computation, 46(10), 1173–1186 (2011).
  6. L.X.C. Ngô, J.R. Sendra, F. Winkler, Classification of algebraic ODEs with respect to rational solvability, Contemporary Mathematics, 572, 193–210 (2012).
  7. L.X.C. Ngô, J.R. Sendra, F. Winkler, Birational transformations on algebraic ordinary differential equations, RISC-Report 2012-18(2012).
/var/www/wiki/htdocs/data/pages/public/events/specsem2013/workshop3.txt · Last modified: 2013/11/21 08:35 by Specsem 2013