Peter Bürgisser

Peter Bürgisser, Felipe Cucker

We describe algorithms for computing eigenpairs (eigenvalue--eigenvector) of a complex $n\times n$ matrix $A$. These algorithms are numerically stable, strongly accurate, and theoretically efficient (i.e., polynomial-time). We do not believe they outperform in practice the algorithms currently used for this computational problem. The merit of our paper is to give a positive answer to a long-standing open problem in numerical linear algebra.

Peter Bürgisser

The numerical condition of the problem of intersecting a fixed $m$-dimensional irreducible complex projective variety $Z\subseteq\mathbb{P}^n$ with a varying linear subspace $L\subseteq\mathbb{P}^n$ of complementary dimension $s=n-m$ is studied. We define the intersection condition number $κ_Z(L,z)$ at a smooth intersection point $z\in Z\cap L$ as the norm of the derivative of the locally defined solution map $\mathbb{G}(s,\mathbb{P}^n)\to\mathbb{P}^n,\, L\mapsto z$. We show that $κ_Z(L,z) = 1/\sinα$, where $α$ is the minimum angle between the tangent spaces $T_zZ$ and $T_zL$. From this, we derive a condition number theorem that expresses $1/κ_Z(L,z)$ as the distance of $L$ to the local Schubert variety, which consists of the linear subspaces having an ill-posed intersection with $Z$ at $z$. A probabilistic analysis of the maximum condition number $κ_Z(L) := \max κ_Z(L,z_i)$, taken over all intersection points $z_i\in Z\cap L$, leads to the study of the volume of tubes around the Hurwitz hypersurface $Σ(Z)$. As a first step towards this, we express the volume of $Σ(Z)$ in terms of its degree.

Diego Armentano, Carlos Beltrán, Peter Bürgisser et al.

Smale's 17th problem asks for an algorithm which finds an approximate zero of polynomial systems in average polynomial time (see Smale 2000). The main progress on Smale's problem is Beltrán-Pardo (2011) and Bürgisser-Cucker (2010). In this paper we will improve on both approaches and we prove an important intermediate result. Our main results are Theorem 1 on the complexity of a randomized algorithm which improves the result of Beltrán-Pardo (2011), Theorem 2 on the average of the condition number of polynomial systems which improves the estimate found in Bürgisser-Cucker (2010), and Theorem 3 on the complexity of finding a single zero of polynomial systems. This last Theorem is the main result of Bürgisser-Cucker (2010). We give a proof of it relying only on homotopy methods, thus removing the need for the elimination theory methods used in Bürgisser-Cucker (2010). We build on methods developed in Armentano et al. (2015).

Diego Armentano, Carlos Beltrán, Peter Bürgisser et al.

We describe algorithms for computing eigenpairs (eigenvalue-eigenvector pairs) of a complex $n\times n$ matrix $A$. These algorithms are numerically stable, strongly accurate, and theoretically efficient (i.e., polynomial-time). We do not believe they outperform in practice the algorithms currently used for this computational problem. The merit of our paper is to give a positive answer to a long-standing open problem in numerical linear algebra.