Search

Can an ideal I in a polynomial ring k[x] over a field be moved by a change of coordinates into a position where it is generated by binomials $x^a - cx^b$ with c in k, or by unital binomials (i.e., with c = 0 or 1)? Can a variety be moved into a position where it is toric? By fibering the G-translates of I over an algebraic group G acting on affine space, these problems are special cases of questions about a family F of ideals over an arbitrary base B. The main results in this general setting are algorithms to find the locus of points in B over which the fiber of F - is contained in the fiber of a second family F' of ideals over B; - defines a variety of dimension at least d; - is generated by binomials; or - is generated by unital binomials. A faster containment algorithm is also presented when the fibers of F are prime. The big-fiber algorithm is probabilistic but likely faster than known deterministic ones. Applications include the setting where a second group T acts on affine space, in addition to G, in which case algorithms compute the set of G-translates of I - whose stabilizer subgroups in T have maximal dimension; or - that admit a faithful multigrading by $Z^r$ of maximal rank r. Even with no ambient group action given, the final application is an algorithm to - decide whether a normal projective variety is abstractly toric. All of these loci in B and subsets of G are constructible; in some cases they are closed., Comment: 22 pages

Structured Low-Rank Approximation is a problem arising in a wide range of applications in Numerical Analysis and Engineering Sciences. Given an input matrix $M$, the goal is to compute a matrix $M'$ of given rank $r$ in a linear or affine subspace $E$ of matrices (usually encoding a specific structure) such that the Frobenius distance $\lVert M-M'\rVert$ is small. We propose a Newton-like iteration for solving this problem, whose main feature is that it converges locally quadratically to such a matrix under mild transversality assumptions between the manifold of matrices of rank $r$ and the linear/affine subspace $E$. We also show that the distance between the limit of the iteration and the optimal solution of the problem is quadratic in the distance between the input matrix and the manifold of rank $r$ matrices in $E$. To illustrate the applicability of this algorithm, we propose a Maple implementation and give experimental results for several applicative problems that can be modeled by Structured Low-Rank Approximation: univariate approximate GCDs (Sylvester matrices), low-rank Matrix completion (coordinate spaces) and denoising procedures (Hankel matrices). Experimental results give evidence that this all-purpose algorithm is competitive with state-of-the-art numerical methods dedicated to these problems., Comment: 37 pages, Maple package available at http://www.pjspaenlehauer.net/data/software/NewtonSLRA_notes.html

Let V be a smooth equidimensional quasi-affine variety of dimension r over the complex numbers $C$ and let $F$ be a $(p\times s)$-matrix of coordinate functions of $C[V]$, where $s\ge p+r$. The pair $(V,F)$ determines a vector bundle $E$ of rank $s-p$ over $W:=\{x\in V:\mathrm{rk} F(x)=p\}$. We associate with $(V,F)$ a descending chain of degeneracy loci of E (the generic polar varieties of $V$ represent a typical example of this situation). The maximal degree of these degeneracy loci constitutes the essential ingredient for the uniform, bounded error probabilistic pseudo-polynomial time algorithm which we are going to design and which solves a series of computational elimination problems that can be formulated in this framework. We describe applications to polynomial equation solving over the reals and to the computation of a generic fiber of a dominant endomorphism of an affine space., 24 pages, accepted for publication in Found. Comput. Math

We continue the study of counting complexity begun in [13], [14], [15] by proving upper and lower bounds on the complexity of computing the Hilbert polynomial of a homogeneous ideal. We show that the problem of computing the Hilbert polynomial of a smooth equidimensional complex projective variety can be reduced in polynomial time to the problem of counting the number of complex common zeros of a finite set of multivariate polynomials. The reduction is based on a new formula for the coefficients of the Hilbert polynomial of a smooth variety. Moreover, we prove that the more general problem of computing the Hilbert polynomial of a homogeneous ideal is polynomial space hard. This implies polynomial space lower bounds for both the problems of computing the rank and the Euler characteristic of cohomology groups of coherent sheaves on projective space, improving the #P-lower bound in Bach [1]. © 2005 Society for the Foundations of Computational Mathematics.

The existence of string functions, which are not polynomial time computable, but whose graph is checkable in polynomial time, is a basic assumption in cryptography. We prove that in the framework of algebraic complexity, there are no such families of polynomial functions of polynomially bounded degree over fields of characteristic zero. The proof relies on a polynomial upper bound on the approximative complexity of a factor g of a polynomial f in terms of the (approximative) complexity of f and the degree of the factor g. This extends a result by Kaltofen (STOC 1986). The concept of approximative complexity allows to cope with the case that a factor has an exponential multiplicity, by using a perturbation argument. Our result extends to randomized (two-sided error) decision complexity., Comment: This is an updated version of a paper published in J. FoCM in 2004. Here we have corrected an error in the statement and proof of Theorem 5.7