Spherical Radon transform and the average of the condition number on certain Schubert subvarieties of a Grassmannian

We study the average complexity of certain numerical algorithms when adapted to solving systems of multivariate polynomial equations whose coefficients belong to some fixed proper real subspace of the space of systems with complex coefficients. A particular motivation is the study of the case of sys...

Full description

Saved in:
Bibliographic Details
Published in:Journal of Complexity 2012-06, Vol.28 (3), p.388-421
Main Authors: Berthomieu, Jérémy, Pardo, Luis Miguel
Format: Article
Language:English
Subjects:
Approximate zero theory
Computational complexity
Computer Science
Probabilistic polynomial time
Smale’s 17th problem
Symbolic Computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the average complexity of certain numerical algorithms when adapted to solving systems of multivariate polynomial equations whose coefficients belong to some fixed proper real subspace of the space of systems with complex coefficients. A particular motivation is the study of the case of systems of polynomial equations with real coefficients. Along these pages, we accept methods that compute either real or complex solutions of these input systems. This study leads to interesting problems in Integral Geometry: the question of giving estimates on the average of the normalized condition number along great circles that belong to a Schubert subvariety of the Grassmannian of great circles on a sphere. We prove that this average equals a closed formula in terms of the spherical Radon transform of the condition number along a totally geodesic submanifold of the sphere.
ISSN:0885-064X
1090-2708
DOI:10.1016/j.jco.2011.11.005