Michael Shub

Felipe Cucker, Teresa Krick, Michael Shub

We describe and analyze a numerical algorithm for computing the homology (Betti numbers and torsion coefficients) of real projective varieties. Here numerical means that the algorithm is numerically stable (in a sense to be made precise). Its cost depends on the condition of the input as well as on its size and is singly exponential in the number of variables (the dimension of the ambient space) and polynomial in the condition and the degrees of the defining polynomials. In addition, we show that outside of an exceptional set of measure exponentially small in the size of the data, the algorithm takes exponential time.

Carlos Beltran, Michael Shub

These pages contain a short overview on the state of the art of efficient numerical analysis methods that solve systems of multivariate polynomial equations. We focus on the work of Steve Smale who initiated this research framework, and on the collaboration between Stephen Smale and Michael Shub, which set the foundations of this approach to polynomial system--solving, culminating in the more recent advances of Carlos Beltran, Luis Miguel Pardo, Peter Buergisser and Felipe Cucker.

Diego Armentano, Michael Shub

In his 1981 Fundamental Theorem of Algebra paper Steve Smale initiated the complexity theory of finding a solution of polynomial equations of one complex variable by a variant of Newton's method. In this paper we reconsider his algorithm in the light of work done in the intervening years. Smale's upper bound estimate was infinite average cost. Our's is polynomial in the Bézout number and the dimension of the input. Hence polynomial for any range of dimensions where the Bézout number is polynomial in the input size. In particular not just for the case that Smale considered but for a range of dimensions as considered by Bürgisser-Cucker where the max of the degrees is greater than or equal to $n^{1+ε}$ for some fixed $ε$. It is possible that Smale's algorithm is polynomial cost in all dimensions and our main theorem raises some problems that might lead to a proof of such a theorem.

Michael Shub, Qing Xu, Xiaohua et al.

In this paper, we propose a maximum entropy method for predicting disease risks. It is based on a patient's medical history with diseases coded in ICD-10 which can be used in various cases. The complete algorithm with strict mathematical derivation is given. We also present experimental results on a medical dataset, demonstrating that our method performs well in predicting future disease risks and achieves an accuracy rate twice that of the traditional method. We also perform a comorbidity analysis to reveal the intrinsic relation of diseases.

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.

Diego Armentano, Carlos Beltrán, Michael Shub

We describe two algorithms for the eigenvalue, eigenvector problem which, on input a Gaussian matrix with complex entries, finish with probability 1 and in average polynomial time.

Michael Shub

We introduce a new complexity measure of a path of (problems, solutions) pairs in terms of the length of the path in the condition metric which we define in the article. The measure gives an upper bound for the number of Newton steps sufficient to approximate the path discretely starting from one end and thus produce an approximate zero for the endpoint. This motivates the study of short paths or geodesics in the condition metric.