2.3 Gaussian Elimination Algorithm.......................... 7 (2009)
Angel D Az, Ioannis Z. Emiris, Erich Kaltofen, Victor Y. Pan
1
Abstract Asymptotic Acceleration of Solving Multivariate Polynomial Systems of Equations (2009)
Bernard Mourrain, Victor Y. Pan
We propose new Las Vegas randomized algorithms for the solution of a multivariate generic or sparse polynomial system of equations. The algorithms use...
Abstract Fast Rectangular Matrix Multiplications and Improving Parallel Matrix Computations * (2008)
Galil and Pan, 1984, reduced parallel evaluation of the inverse, the determinant and the characteristic polynomial of a matrix and solving a nonsingular linear system of equw tions to sequential...
Abstract The structure of sparse resultant matrices (2008)
Ioannis Z. Emiris, Victor Y. Pan
Resultants characterize the existence of roots of systems of multivariate nonlinear polynomial equations, while their matrices reduce the computation of all common zeros to a problem in linear...
2.3 Gaussian Elimination Algorithm.......................... 7 (2008)
Angel D Az, Ioannis Z. Emiris, Erich Kaltofen, Victor Y. Pan
1
Abstract. Computations with Toeplitz and Toeplitz-like matrices are fundamental for many areas of algebraic and numerical computing. The list of computational problems reducible to Toeplitz and...
Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision (2007)
Hervé Brönnimann, Herv Br#nnimann, Ioannis Z. Emiris, Sylvain Pion, Victor Y. Pan
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
Angel Díaz, Ioannis Z. Emiris, Erich Kaltofen, Victor Y. Pan
This article, along with [Elkadi and Mourrain 1996], explain the correlation between residue theory and the Dixon matrix, which yields an alternative method for studying and approximating all common...
Computing Exact Geometric Predicates Using Modular Arithmetic With Single Precision (2007)
Herv Brnnimann Ioannis, Herv Br#nnimann, Ioannis Z. Emiris, Victor Y. Pan
: We propose an eOEcient method that determines the sign of a multivariate polynomial expression with integer coeOEcients. This is a central operation on which the robustness of many geometric...
Ioannis Z. Emiris, Erich Kaltofen, Victor Y. Pan
1 Supported by NSF grant No. CCR-9319776 and by GTE under a Graduate Computer Science Fellowship. 2 Supported by the European Union under ESPRIT FRISCO project LTR 21.024. 3 Supported by NSF grant...
Solution of a polynomial system of equations via the eigenvector computation (2007)
Didier Bondyfalat, Bernard Mourrain, Victor Y. Pan
We propose new techniques and algorithms for the solution of a polynomial system of equations by matrix methods. For such a system, we seek its specied root, at which a xed polynomial takes its...
Didier Bondyfalat, Bernard Mourrain, Victor Y. Pan
For a system of polynomial equations, we seek its speci-ed root, maximizing or minimizing the absolute value of a xed polynomial over all roots of the system. The latter requirement to a root,...
Didier Bondyfalat, Bernard Mourrain, Victor Y. Pan
of a specied root of a polynomial system of equations using eigenvectors
Summary We modify our earlier homotopic process for iterative inversion of Toeplitz and Toeplitz-like matrices to improve the choice of the initial approximate inverses at every homotopic step. This...
Iterative Inversion of Structured Matrices ∗ (2002)
Gianni Codevico, Victor Y. Pan, Marc Van, Barel Xinmao Wang, Gianni Codevico, Victor Y. Pan, ...
Iterative processes for the inversion of structured matrices can be further improved by using a technique for compression and refinement via the least-squares computation. We review such processes...
Univariate polynomials: Nearly optimal algorithms for numerical factorization and rootfinding (2001)
To approximate all roots (zeros) of a univariate polynomial, we develop two effective algorithms and combine them in a single recursive process. One algorithm computes a basic well isolated zero-free...
Multivariate polynomials, duality and structured matrices (2000)
Bernard Mourrain, Victor Y. Pan
We rst review the basic properties of the well known classes of Toeplitz, Hankel, Vandermonde, and other related structured matrices and reexamine their correlation to operations with univariate...
Multivariate polynomials, duality and structured matrices (2000)
Bernard Mourrain, Victor Y. Pan
We rst review the basic properties of the well known classes of Toeplitz, Hankel, Vandermonde, and other related structured matrices and reexamine their correlation to operations with univariate...
New Arithmetic Filter for the Sign of the Determinant of a Matrix (1999)
Certified sign of the determinant of a matrix is very frequently required in various geometric and algebraic computations. The computations go faster when they are performed numerically, with oating...
Sign Determination in Residue Number Systems (1999)
Herv Brnnimann Ioannis, Herv Br#nnimann, Ioannis Z. Emiris, Victor Y. Pan
Sign determination is a fundamental problem in algebraic as well as geometric computing. It is the critical operation when using real algebraic numbers and exact geometric predicates. We propose an...
Sign Determination in Residue Number Systems (1999)
Hervé Brönnimann, Herv Br#nnimann, Ioannis Z. Emiris, Sylvain Pion, Victor Y. Pan
Sign determination is a fundamental problem in algebraic as well as geometric computing. It is the critical operation when using real algebraic numbers and exact geometric predicates. We propose an...
A Unified Superfast Divide-and-Conquer Algorithm for Structured Matrices Over Fields (1999)
We propose a superfast divide-and-conquer algorithm that uses 2n - 2 random parameters, O(n) memory space and O((n log² n) log log n) operations in a fixed arbitrary field in order to compute...
1 Computations with Toeplitz and Toeplitz-like matrices are fundamental for many areas of algebraic and numerical computing. The list of computational problems reducible to Toeplitz and Toeplitz-like...
Fast Cauchy-like and Singular Toeplitz-like Matrix Computations (1999)
s. We avoid singularity in this algorithm and run it in an arbitrary field by using randomization. We also ameliorate slightly Kaltofen's solver of Toeplitz-like singular linear systems in an...
Fields Victor Y. Pan Department of Mathematics & Computer Science, Lehman College, CUNY Bronx, NY 10468 Internet address: vpan@lcvax.lehman.cuny.edu February 19, 1999 Abstract We study...
Bisection Acceleration for the Symmetric Tridiagonal Eigenvalue Problem (1999)
We present new algorithms that accelerate the bisection method for the symmetric tridiagonal eigenvalue problem. The algorithms rely on some new techniques, including a new variant of Newton's...
Ioannis Z. Emiris, Victor Y. Pan
Introduction The subject of this chapter lies in the area of theoretical computer science, though it borrows certain results from computational mathematics, and is fundamental to the theory and...
Sign determination in residue number systems (1999)
Hervé Brönnimann, Ioannis Z. Emiris, Victor Y. Pan
Sign determination is a fundamental problem in algebraic as well as geometric computing. It is the critical operation when using real algebraic numbers and exact geometric predicates. We propose an...
Multivariate Polynomials, Duality and Structured Matrices (1998)
Mourrain, Bernard, Pan, Victor Y.
We re-investigate the well known classes of Toeplitz, Hankel, Vandermonde, and other related structured matrices, by re-examining their correlations to operations with univariate polynomials. Then we...
Multivariate Polynomials, Duality and Structured Matrices (1998)
Mourrain, Bernard, Pan, Victor Y.
We re-investigate the well known classes of Toeplitz, Hankel, Vandermonde, and other related structured matrices, by re-examining their correlations to operations with univariate polynomials. Then we...
Multivariate Polynomials, Duality and Structured Matrices (1998)
Mourrain, Bernard, Pan, Victor Y.
We re-investigate the well known classes of Toeplitz, Hankel, Vandermonde, and other related structured matrices, by re-examining their correlations to operations with univariate polynomials. Then we...
Modular Arithmetic for Linear Algebra Computations in the Real Field (1998)
Ioannis Z. Emiris, Yanqiang Yu, Victor Y. Pan
The aim of this work is to decrease the bit precision required in communications without affecting the precision of the answer...
The Complexity of the Algebraic Eigenproblem (1998)
Victor Y. Pan, Zhao Q. Chen, Ailong Zheng
The eigenproblem for an n-by-n matrix A is the problem of the approximation (within a relative error bound 2 \Gammab ) of all the eigenvalues of the matrix A and computing the associated eigenspaces...
Lifting/Descending Processes for Polynomial Zeros (1998)
Bernard Mourrain, Victor Y. Pan
The recently proposed Chebyshev-like lifting map for the zeros of a univariate polynomial was motivated by its applications to splitting a univariate polynomial p(x) numerically into factors, which...
Controlled Iterative Methods for Solving Polynomial Systems (1998)
Didier Bondyfalat, Bernard Mourrain, Victor Y. Pan
For a system of polynomial equations, we seek its specified root, maximizing or minimizing the absolute value of a fixed polynomial over all roots of the system. The latter requirement to a root,...
Some Recent Algebraic/Numerical Algorithms (1998)
Combination of algebraic and numerical techniques for improving the computations in algebra and geometry is a popular research topic of growing interest. We survey some recent progress that we made...
Certified Numerical Computation of the Sign of a Matrix Determinant (1998)
Certified computation of the sign of a matrix determinant is a central problem in computational geometry. The certification by the known methods is practically difficult because the magnitude of the...
Multivariate Polynomials, Duality, and Structured Matrices (1998)
Bernard Mourrain, Victor Y. Pan
We first review the basic properties of the well known classes of Toeplitz, Hankel, Vandermonde, and other related structured matrices and re-examine their correlations to operations with univariate...
Computing Matrix Eigenvalues And Polynomial Zeros Where The Output Is Real (1998)
.<F3.809e+05> Surprisingly simple corollaries from the Courant--Fischer minimax characterization theorem enable us to devise a very e#ective algorithm for the evaluation of a...
Asymptotic Acceleration of Solving Multivariate Polynomial Systems of Equations (1998)
Bernard Mourrain, Victor Y. Pan
We propose new Las Vegas randomized algorithms for the solution of a multivariate generic or sparse polynomial system of equations. The algorithms use O ((ffi+4 n )3 n D 2 log b) arithmetic...
Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision (1997)
Brönnimann, Hervé, Emiris, Ioannis Z., Pan, Victor Y., Pion, Sylvain
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision (1997)
Brönnimann, Hervé, Emiris, Ioannis Z., Pan, Victor Y., Pion, Sylvain
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision (1997)
Brönnimann, Hervé, Emiris, Ioannis Z., Pan, Victor Y., Pion, Sylvain
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
Exact Modular Arithmetic With Single Precision (1997)
Hervé Brönnimann, Herv Br#nnimann, Ioannis Z. Emiris, Sylvain Pion, Victor Y. Pan
Sign determination is a fundamental problem in algebraic as well as geometric computing. It is the critical operation when using real algebraic numbers and exact geometric predicates. We propose an...
Symbolic and Numeric Methods for Exploiting Structure in Constructing Resultant Matrices (1997)
Ioannis Z. Emiris, Victor Y. Pan
This paper identifies and exploits the structure of Newton matrices by designing an efficient numerical rank test and exact polynomial arithmetic in the context of sparse elimination. This yields...
Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision (1997)
Hervé Brönnimann, Herv Br#nnimann, Ioannis Z. Emiris, Sylvain Pion, Ioannis Z. Emiris, Victor Y. Pan, ...
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
Multidimensional Structured Matrices and Polynomial Systems (1997)
Bernard Mourrain, Bernard Mourrain Inria, Victor Y. Pan
We apply and extend some well-known and some recent techniques from algebraic residue theory in order to relate to each other two major subjects of algebraic and numerical computing, that is,...
Solving Special Polynomial Systems By Using Structured Matrices and Algebraic Residues (1997)
Bernard Mourrain, Victor Y. Pan
We apply and extend some well-known and some recent techniques from algebraic residue theory in order to relate to each other two major subjects of algebraic and numerical computing, that is,...
New Techniques for Decoding the BCH Error-Correcting Codes (1997)
The coefficients of a polynomial of a degree n can be expressed via the power sums of its zeros by means of a polynomial equation known as the key equation for decoding the BCH error-correcting...
The Structure of Sparse Resultant Matrices (1997)
Ioannis Z. Emiris, Victor Y. Pan
Resultants characterize the existence of roots of systems of multivariate nonlinear polynomial equations, while their matrices reduce the computation of all common zeros to a problem in linear...
Solving A Polynomial Equation: Some History And Recent Progress (1997)
The classical problem of solving an nth degree polynomial equation has substantially influenced the development of mathematics throughout the centuries and still has several important applications to...
Parallel Matrix Multiplication on a Linear Array with a Reconfigurable Pipelined Bus System (1997)
Keqin Li, Keqin Li, Victor Y. Pan, Victor Y. Pan
The known fast sequential algorithms for multiplying two N \Theta N matrices (over an arbitrary ring) have time complexity O(N ff ), where 2 ! ff ! 3. The current best value of ff is less than...
Numerical Computation of a Polynomial GCD and Extensions (1996)
In the first part of this paper, we define approximate polynomial gcds (greatest common divisors) and extended gcds provided that approximations to the zeros of the input polynomials are available....
The known record complexity estimates for approximating polynomial zeros rely on geometric constructions on the complex plane, which achieve initial approximation to the zeros and/or their clusters...
Numerical Computation of a Polynomial GCD and Extensions (1996)
In the first part of this paper, we define approximate polynomial gcds (greatest common divisors) and extended gcds provided that approximations to the zeros of the input polynomials are available....
The known record complexity estimates for approximating polynomial zeros rely on geometric constructions on the complex plane, which achieve initial approximation to the zeros and/or their clusters...
Numerical Computation of a Polynomial GCD and Extensions (1996)
In the first part of this paper, we define approximate polynomial gcds (greatest common divisors) and extended gcds provided that approximations to the zeros of the input polynomials are available....
The known record complexity estimates for approximating polynomial zeros rely on geometric constructions on the complex plane, which achieve initial approximation to the zeros and/or their clusters...
Numerical Computation Of A Polynomial GCD And Extensions (1996)
Projet Safir, Victor Y. Pan, Victor Y. Pan, Victor Y. Pan
In the first part of this paper, we dene approximate polynomial gcds (greatest common divisors) and extended gcds provided that approximations to the zeros of the input polynomials are available. We...
The known record complexity estimates for approximating polynomial zeros rely on geometric constructions on the complex plane, which achieve initial approximation to the zeros and/or their clusters...
We propose a new algorithm for the classical and still practically important problem of approximating the zeros z j of an n-th degree polynomial p(x) within the error bound 2 \Gammab max j jz j j....