PUBLICATIONS

Research Monographs

4. Polynomial and Matrix Computations, Volume 2: Selected Topics (with D. Bini), Birkhaeuser, Boston (2004) to appear.

3. Structured Matrices and Polynomials: Unified Superfast Algorithms, Birkhaeuse/Springer, Boston/New York (2001).

2. Polynomial and Matrix Computations, Volume 1: Fundamental Algorithms (XVI + 415 pages) (with D. Bini), in the series Progress in Theoretical Computer Science (R.V. Book editor), Birkhaeuser, Boston (1994).

1. How to Multiply Matrices Faster, Lecture Notes in Computer Science, vol. 179 (212 pages), Springer Verlag, Berlin (1984).



Chapters in Books and Survey Articles (items 1, 3, 4, 5, 8 present new research results)

13. "Fast Fourier Transform and Its Applications" (with I. Z. Emiris), Chapter 18 in Handbook "Algorithms and Theory of Computations", ch. 17, pp. 17-1 to 17-30, M. Atallah, editor, CRC Press Inc., Boca Raton, Florida (1999).

12. "Algebraic Algorithms" (with A. Diaz, I. Z. Emiris, and E. Kaltofen), Chapter 17 in Handbook "Algorithms and Theory of Computations", ch. 16, pp. 16-1 to 16-27, M. Atallah, editor, CRC Press Inc., Boca Raton (1999).

11. "Some Recent Algebraic/Numerical Algorithms", Electronic Proceedings of IMACS/ACA ‘98.

10. "Computational Complexity of Solving Large Sparse and Large Special Linear Systems of Equations", pp. 1-24, in "Algorithms for Large Scale Linear Algebraic Systems: Applications in Science and Engineering", G. Winter Althaus and E. Spedicato editors, NATO Advanced Science Institute Series, Kluwer Academic Publishers , Dordrecht, The Netherlands

9. "Solving Polynomials with Computers", American Scientist, 86, 62-69, (January-February 1998).

8. "Solving a Polynomial Equation: Some History and Recent Progress", SIAM Review, 39, 2, 187-220 (1997).

7. "Algebraic Algorithms" (with A. Diaz and E. Kaltofen), Chapter 10 in The Computer Science and Engineering Handbook, Alllen B. Tucker, Jr., (editor), 226-249, CRC Press Inc., Boca Raton, Florida (1997).

6. "Parallel Solution of Sparse Linear and Path Systems", in Synthesis of Parallel Algorithms (J.H. Reif editor), Chapter 14, pp. 621-678. Morgan Kaufmann publishers, San Mateo, California (1993).

5. "Complexity of Computations with Matrices and Polynomials," SIAM Review, 34, 2, 225-262 (1992).

4. "Complexity of Algorithms for Linear Systems of Equations", in Computer Algorithms for Solving Linear Algebraic Equations (The State of the Art), edited by E. Spedicato, NATO ASI Series, Series F: Computer and Systems Sciences, 77, 27-56, Springer, Berlin (1991) and Academic Press (1992).

3. "Linear Systems of Algebraic Equations", in Encyclopedia of Physical Sciences and Technology, 7, 304-329 (1987), (first edition, Marvin Yelles, editor); 8, 779-804 (1992) (second edition); and 8, (2001) (third edition, Robert A. Meyers, editor); Academic Press, San Diego, California.

2. “How Can We Speed Up Matrix Multiplication?", SIAM Review, 26, 3, 393-415 (1984).

1. On Methods of Computing the Values of Polynomials", Uspekhi Matematicheskikh Nauk, 21,1 (127), 103-134 (1966).(Transl. Russian Mathematical Surveys, 21,1 (127), 105-137 (1966).)


Research Articles (in journals and refereed proceedings of conferences)

215. "Toeplitz and Hankel Meet Hensel and Newton Modulo a Power of Two" (by V. Y. Pan, B. Murphy, R. E. Rosholt and X. Wang), preprint (2005).

214. "A Homotopic/Factorization Process for Toeplitz-like Matrices with Newton’s/Conjugate Gradient Stages", preprint (2005).

213. “Homotopic Residual Correction Algorithms for General and Structures Matrices" (by V.Y. Pan, M. Kunin, R. Rosholt, and H. Kodal), Math. of Computation, in press.

212. “The Amended DSeSC Power Method for Polynomial Root-finding”, Computers and Mathematics with Applications, in press.

211. “Coefficient-free Adaptation of Polynomial Root-finders”, Computers and Mathematics with Applications, in press.

210. "The Perturbation/Realization Approach to the Matrix Eigenproblem" (by V. Y. Pan, B. Murphy, R. E. Rosholt, X. Wang), Computers and Mathematics with Applications, in press.

209. "Fast and Stable QR Eigenvalue Algorithms for Generalized Semiseparable Matrices and Secular Equations" (by D.A. Bini, L. Gemignani and V.Y. Pan), Numerische Mathematik, in press.

208. "Can the TPR1 Structure Help Us to Solve the Algebraic Eigenproblem?”, in Proc. of the 16th Ann. ACM-SIAM Symposium on Discrete Algorith (SODA ‘05), 1069-1078, ACM Press, New York, and SIAM Publications, Philadelphia (January 2005).

207. “ Improved Algorithms for Computing Determinants and Resultants" (by I. Z. Emiris and V. Y. Pan), J. of Complexity, 21, 1, 43-71 (2005).

206. “An Efficient Solution for Cauchy-like Systems of Linear Equations” (by Z. Chen and V. Y. Pan), Computers and Mathematics with Applications, 48, 529-537 (2004).

205. “On Theoretical and Practical Acceleration of Randomized Computation of the Determinant of an Integer Matrix” , Zapiski Nauchnykh Seminarov POMI (in English), Vol. 316, St. Petersburg, Russia (2004).

204. "Improved Initialization of the Accelerated and Robust QR-like Polynomial Root-finding" (by D. A. Bini, L. Gemignani, and V. Y. Pan), Electronic Transactions on Numerical Analysis, 17, 195-205 (2004). (Proc. version in Proceedings of the 7th International Workshop on Computer Algebra in Scientific Computing (CASC ‘04), St. Petersburg, Russia (July 2004), (edited by E. W. Mayr, V. G. Ganzha, E. V. Vorozhtzov), 39-50, Technische Univ. München, Germany (2004).) Proceedings Version

 Also: Journal Version

203. “Newton-like Iteration Based on Cubic Polynomials for Structured Matrices” (by G. Codevico, V. Y. Pan, and M. Van Barel), Numerical Algorithms, 36, 365-380 (2004).

202. "The Least-Squares Compression Policy for Newton-like Iteration for Structured Matrices" (by G. Codevico, V.Y. Pan, M. Van Barel, X. Wang, and A.-L. Zheng) in Proceedings of the 6th International Mathematica Symposium (IMS 2004) (edited by C. Jacob and P. Mitic), Banff, Alberta, Canada (August 2004).

201. "Iterative Inversion of Structured Matrices" (by V. Y. Pan, M. Van Barel, X. Wang and G. Codevico), Theoretical Computer Science, 315, 2-3, 581-592 (2004).

200. "On Rational Number Reconstruction and Approximation" (by V. Y. Pan and X. Wang), SIAM J. on Computing, 33, 2, 502-503 (2004).

199. "Inverse Power and Durand-Kerner Iteration for Univariate Polynomial Root-Finding "(by D.A. Bini, L. Gemignami and V.Y. Pan), Computers and Mathematics (with Applications), 2003.

198. "Improved Computation of Determinants and Resultants" (by I.Z. Emiris and V.Y. Pan), Proc. of the 6th International Workshop on Computer Algebra in Scientific Computing (CASC '03), (E.W. Mayr, V.G. Ganzha, E.V. Vorozhtzov, Editors), 81-94, Technische Univ. Muenchen, Germany, 2003.

197. "Acceleration of Euclidean Algorithm and Rational Number Reconstruction", (by X. Wang and V. Y. Pan), SIAM J. of Computing, 32, 2, 548-556 (2003).

196. "Matrix Structure and Loss-Resilient Encoding/Decoding", Computers & Mathematics (with Applications), 46, 493-499 (2003).

195. "Inversion of Displacement Operators", (by V.Y. Pan and X. Wang), SIAM J. on Matrix Analysis and Applications, 24, 3, 660-677 (2003).

194. "Accelerated Solution of Multivariate Polynomial Systems of Equations", (by B. Mourrain, V.Y. Pan, and O. Ruatta), SIAM J. on Computing, 32, 2, 435-454 (2003).

193. "Can We Optimize Toeplitz/Hankel Computations? ", Proc. of the 5th International Workshop on Computer Algebra in Scientific Computing (CASC ‘02), ( E. W. Mayr, V. G. Ganzha, E. V. Vorozhtzov, Editors), 253-264, Technische Univ. Muenchen, Germany (2002).

192. "Univariate Polynomials: Nearly Optimal Algorithms for Numerical Factorization and Root-Finding", J. of Symbolic Computation, 33, 5, 701-733 (2002)

191. "Acceleration of Euclidean Algorithm and Extensions", (by V.Y. Pan and X. Wang), Proc. International Symp. on Symbolic and Algebraic Computation, (ISSAC ‘02), 207-213, ACM Press, New York (2002).

190. "Symbolic and Numerical Methods for Exploiting Structure in Constructing Resultant Matrices", (by I. Z. Emiris and V.Y. Pan), Journal of Symbolic Computation, 33, 393-413 (2002).

189. "Randomized Acceleration of Fundamental Matrix Computations", Proc. of Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, 215-226, Springer, Berlin (2002).

188. "Structured Matrices and Newton’s Iteration: Unified Approach", (by V.Y. Pan, Y. Rami and X. Wang), Linear Algebra and Its Applications, 343/344, 233-265 (2002).

187. "Nearly Optimal Algorithms for Numerical Univariate Polynomial Factorization and Rootfinding I: Splitting a Polynomial into Factors over an Annulus", Proceedings of the Smalefest 2000, F. Cucker and M. Rojas (Eds.), Foundations of Computational Math. Series, 325-353, World Scientific, New Jersey (2002).

186. "Asymptotic Acceleration of the Solution of Multivariate Polynomial Systems of Equations", (by B. Mourrain, V.Y. Pan and O. Ruatta), Proceedings of the Smalefest 2000, F. Cucker and M. Rojas (Eds.), Foundations of Computational Math. Series, 267-294, World Scientific, New Jersey (2002).

184. “Univariate Polynomials: Nearly Optimal Algorithms for Factorization and Rootfinding”, Proc. International Symp. on Symbolic and Algebraic Computation, (ISSAC '01) 253-267, ACM Press, New York (July 2001).

183. "Numerical Computation of a Polynomial GCD and Extensions", Information and Computation, 167, 2, 71-85 (2001). (Only draft available)

182. “Parallel Matrix Multiplication on a Linear Array with a Reconfigurable Pipelined Bus System”, (with Keqin Li), IEEE Transactions on Computing, 50, 5, 519-525, (2001).

181. "Certification of Numerical Computation of the Sign of the Determinant of a Matrix" (with Y. Yu), Algorithmica, 30, 708-724, (2001).

180. “Newton’s Iteration for the Inversion of Structured Matrices” (with Y. Rami), in “Structured Matrices: Recent Developments in Theory and Computation”, 79-90, edited by D. Bini, E. Tyrtyshnikov and P. Yalamov, Nova Science Publishers, USA (2001).

179. “A Homotopic Residual Correction Process”, Proc. of the Second Conference on Numerical Analysis and Applications (L. Vulkov, J. Wasniewsky and P. Yalamov, editors), Lecture Notes in Computer Science, 1988, 644-649, Springer, Berlin (2001).

178. “A New Proximity Test for Polynomial Zeros,” Computers & Math. (with Applications), 41, 12, 1559-1560 (2001).

177. “Computation of a Specified Root of a Polynomial System of Equations Using Eigenvectors “ (with D. Bondyfalat and B. Mourrain), Linear Algebra and Its Applications, 319, 193-209 (2000).

176. “Parallel Complexity of Computations with General and Toeplitz-like Matrices Filled with Integers”, SIAM J. on Computing, 30, 1080-1125 (2000).

175. “Matrix Structure, Polynomial Arithmetic, and Erasure-Resilient Encoding/Decoding,”, Proc. Intern. Symp. on Symbolic and Algebraic Computations (ISSAC ‘2000), 266-271, ACM Press, New York (2000).

174. “Superfast Algorithms for Cauchy-like Matrix Computations and Extensions” (with A. Zheng), Linear Algebra and Its Applications, 310, 83-108 (2000).

173. “New Techniques for the Computation of Linear Recurrence Coefficients”, Finite Fields and Their Applications, 6, 93-118 (2000).

172. "Lifting/Descending Processes for Polynomial Zeros and Applications" (with B. Mourrain), J. of Complexity, 16, 1, 265-273 (2000).

171. "Multivariate Polynomials, Duality and Structured Matrices" (with B. Mourrain), J. of Complexity, 16, 1, 110-180 (2000).

170."Approximating Complex Polynomial Zeros: Modified Quadtree (Weyl's) Construction and Improved Newton's Iteration", J. of Complexity, 16, 1, 213-264 (2000).

169. “Nearly Optimal Computations with Structured Matrices”, Proc. of 11th Ann. ACM-SIAM Symposium on Discrete Algorithms, 953-962, ACM Press, New York, and SIAM Publications, Philadelphia (January 2000).

168."A New Approach to Bisection Acceleration for the Symmetric Tridiagonal Eigenvalue Problem", (with E. Linzer), Numerical Algorithms, 22, 13-39 (1999).

167. “Polynomial and Rational Interpolation and Multipoint Evaluation (with Structured Matrices)” (with V. Olshevsky), Proc. 26th Intern. Colloquium on Automata, Languages and Programming (ICALP’99), 1644, 585-594, Springer’s Lecture Notes in Computer Science, Springer, Berlin (July 1999).

166. "Superfast Computations with Singular Structured Matrices over Abstract Fields" (with A. Zheng, M. Abutabanjeh, Z. Chen and S. Providence), Proc. Second Workshop on Computer Algebra in Scientific Computing (CASC-99), (V.G. Ganzha, E.W. Mayr, E.V. Vorontsov, Editors), 323-338, Springer (May 1999).

165. "The Complexity of the Matrix Eigenproblem", (with Z. Chen), Proc. 31st Annual ACM Symposium on Theory of Computing, 507-516, ACM Press, New York (1999).

164. "Parallel Matrix Multiplication on a Linear Array with a Reconfigurable Pipelined Bus System" (with Keqin Li), Proc. 13th Intern. Parallel Processing Symp. and 10th Symp. on Parallel and Distributed Computing (IPPS/SPDP 1999), 31-35, IEEE Computer Soc. Press (April 1999).

163. "Newton's Iteration for Structured Matrices and Linear Systems of Equations", (with Sheryl Branham, Rhys Rosholt, and Ailong Zheng), SIAM volume on Fast Reliable Algorithms for Matrices with Structure (T. Kailath and A. Sayed editors), ch. 7, pp. 189-210, SIAM Publications, Philadelphia (1999).

162. "Approximate Real Polynomial Division via Approximate Inversion of Real Triangular Toeplitz Matrices" (with Z.Chen), Applied Math. Letters, 12, 3, 1-2 (1999).

161. "Certified Computation of the Sign of a Matrix Determinant" (with Y. Yu), Proc. 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 715-724, ACM Press, New York, and SIAM Publications, Philadelphia (1999).

160. "Sign Determination in Residue Number Systems" (with H. Bronnimann, I.Z. Emiris, and S. Pion), Theoretical Computer Science, 210, 1, 173-197 (1999).

159."A Unified Superfast Algorithm for Boundary Rational Tangential Interpolation Problem and for Inversion and Factorization of Dense Structured Matrices" (with V. Olshevsky), Proc. 39th Annual IEEE Symposium on Foundation of Computer Science, 192-201, IEEE Computer Society Press (1998).

158."Single Precision Computation of the Sign of Algebraic Predicates", Applied Math. Letters, 11, 6, 49-50 (1998).

157. "Fast Rectangular Matrix Multiplication and Applications" (with Xiaohan Huang), J. of Complexity, 14, 257-299 (1998).

156. "Transformations of Cauchy Matrices for Trummer's Problem and a Cauchy-like Linear Solver" (with M. Abu Tabanjeh, Z. Chen, S. Providence and A. Sadikou), Proc. of 5th Annual International Symposium on Solving Irregularly Structured Problems in Parallel (Irregular 98), (A. Ferreira, J. Rolim, H. Simon, S.-H. Teng, Editors), Lecture Notes in Computer Science, 1457, 274-284, Springer (1998).

155. "Controlled Iterative Methods for Solving Polynomial Systems", (with D. Bondyfalat, B. Mourrain), Proc. ACM Annual Intern. Symp. on Symbolic and Algebraic Comp. (ISSAC '98), 252-259, ACM Press, New York (1998).

154. "Modular Arithmetic for Linear Algebra Computations in the Real Field" (with Ioannis Z. Emiris and Yankiang Yu), J. of Symbolic Computation, 21, 1-17 (1998).

153. "Computing Matrix Eigenvalues and Polynomial Zeros Where the Output Is Real" (with D. Bini), SIAM J. on Computing, 27, 4, 1099-1115 (1998).

152. "Planar Integer Linear Programming Is NC-equivalent to Euclidean GCD" (with D.F. Shallcross and Yu Lin-Kriz), SIAM Journal on Computing, 27, 4, 960-971 (1998).

151. "Asymptotic Acceleration of Solving Polynomial Systems" (with Bernard Mourrain), Proc. 30th Annual ACM Symp. on Theory of Computing, 488-496, ACM Press, New York (1998).

150. "New Transformations of Cauchy Matrices and Trummer's Problem", (with M. Abu Tabanjeh, Z.Q. Chen, E. Landowne, and A. Sadikou), Computers & Mathematics (with Applications), 35, 12, 1-5 (1998).

149. "Approximate Polynomial Gcds, Pade Approximation, Polynomial Zeros, and Bipartite Graphs", Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms, 68-77, ACM Press, New York, and SIAM Publications, Philadelphia (1998).

148. "New Fast Algorithms for Polynomial Interpolation and Evaluation on the Chebyshev Node Set", Computers & Math. (with Applications), 35, 3, 125-129 (1998).

147. "Efficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs" (with Y. Han and J. Reif), Algorithmica, 17, 399-415 (1997).

146. "Algebraic and Numerical Techniques for the Computation of Matrix Determinants" (with Y. Yu and C. Stewart), Computers and Mathematics (with Applications), 34, 1, 43-70 (1997).

145. "Fast Rectangular Matrix Multiplication and Improving Parallel Matrix Computations" (with Xiaohan Huang), Proc. Annual ACM International Symposium on Parallel Algebraic and Symbolic Computations (PASCO ‘97), 11-23, ACM Press, New York (1997).

144. "The Structure of Sparse Resultant Matrices" (with I. Z. Emiris), Proc. Annual ACM International Symposium on Symbolic and Algebraic Computations (ISSAC ‘97), 189-196, ACM Press, New York (1997).

143. "Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision" (with H. Bronnimann, I. Z. Emiris, and S. Pion), Proc. 13th Ann. ACM Symp. On Computational Geometry, 174-182, ACM Press, New York (1997).

142. "Faster Solution of the Key Equation for Decoding the BCH Error-Correcting Codes", Proc. 29th ACM Symposium on Theory of Computing, 168-175, ACM Press, New York (1997).

141. "Newton's Iteration for Inversion of Cauchy-like and Other Structured Matrices" (with A. Zheng, X. Huang, and O. Dias), J. of Complexity, 13, 108-124 (1997).

140. "Fast Multipoint Polynomial Evaluation and Interpolation via Computation with Structured Matrices" (with Ai-Long Zheng, Xiaohan Huang and Yangiang Yu), Annals of Numerical Math., 4, 483-510 (1997).

139. "Solving Special Polynomial Systems by Using Structured Matrices and Algebraic Residues" (with B. Mourrain), Proc. of the AMS-SIAM Conference on Foundation of Computational Math., F. Cucker and M. Shub, editors, Rio-de-Janeiro, January 1997, 287-304, Springer (1997).

138. "Efficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs" (with Y. Han, J. Reif), Algorithmica, 17, 399-415 (1997).

137. "Techniques for Exploiting Structure in Matrix Formulae of the Sparse Resultant (with I.Z. Emiris), Calcolo,  (Special Issue on Toeplitz Matrices: Structure, Algorithms and Applications), 33, 353-369 (1996).

136. "Multidimensional Structured Matrices and Polynomial Systems" (with B. Mourrain), Calcolo, (Special Issue on Toeplitz Matrices: Structure, Algorithms and Applications), 33, 389-401 (1996).

135. "Graeffe's, Chebyshev-like, and Cardinal's Processes for Splitting a Polynomial into Factors" (with D. Bini), J. of Complexity, 12, 492-511 (1996).

134. "On Isolation of Real and Nearly Real Zeros of a Univariate Polynomial and Its Splitting Into Factors" (with M.-h. Kim, A. Sadikou, X. Huang, and A. Zheng), J. of Complexity , 12, 572-594 (1996).

133. "Parallel Computation of Polynomial GCD and Some Related Parallel Computations over Abstract Fields", Theoretical Computer Science, 162, 2, 173-223 (1996).

132. "Effective Parallel Computations with Toeplitz and Toeplitz-like Matrices Filled with Integers", in Proc. of the AMS-SIAM Workshop "Mathematics of Numerical Analysis" (Park City, Utah, July-August 1995) (J. Renegar, M. Shub, S. Smale, editors), Lectures in Applied Math., 32, 593-641, Amer. Math. Society Press, Providence, Rhode Island (1996).

131. "A New Approach to Parallel Computation of Polynomial GCDs and to Related Parallel Computations over Fields and Integer Rings", Proc. 7th Ann. ACM-SIAM Symposium on Discrete Algorithms, 518-527, ACM Press, New York, and SIAM Publications, Philadelphia (1996).

130. "Computing xn mod p(x) and an Application to Splitting a Polynomial into Factors over a Fixed Disc", Journal of Symbolic Computations, 22, 1-4 (1996).

129. "Optimal and Nearly Optimal Algorithms for Approximating Polynomial Zeros", Computers & Math. (with Applications), 31, 12, 97-138 (1996).

128. "A Fast, Preconditioned Conjugate Gradient Toeplitz and Toeplitz-like Solver" (with Zheng Ai-Long, Olen Dias and Xiaohan Huang), Computers & Math. (with Applications), 30, 8, 57-63 (1995).

127."Weyl's Quadtree Algorithm for Unsymmetric Eigenvalue Problem", Applied Math. Letters, 8, 5, 87-88 (1995)

126. "Optimal (up to Polylog Factors) Sequential and Parallel Algorithms for Approximating Complex Polynomial Zeros", Proc. 27th Ann. ACM Symposium on Theory of Computing, 741-750, ACM Press, New York (1995).

125. "On Parallel Computations with Band Matrices" (with I. Sobze and A. Atinkpahoun), Information and Computation, 120, 2, 237-250 (1995).

124. "Deterministic Improvement of Complex Polynomial Factorization Based on the Properties of the Associated Resultant", Computers & Math. (with Applications), 30, 2, 71-94 (1995).

123. "Parallel Computation of a Krylov Matrix for a Sparse and Structured Input", Mathematical and Computer Modelling, 21, 11, 97-99 (1995).

122. "Work-Preserving Speed-up of Parallel Matrix Computations" (with F.P. Preparata), SIAM J. on Computing, 24, 4, 811-821 (1995).

121. "An Algebraic Approach to Approximate Evaluation of a Polynomial on a Set of Real Points",  Advances in Computational Mathematics, 3, 41-58 (1995).

120. "Algebraic Improvement of Numerical Algorithms: Interpolation and Economization of Taylor Series", Mathematical and Computer Modelling, 20, 1, 23-26 (1994).

119. "Parallel Solution of Toeplitz and Toeplitz-like Linear Systems over Fields of Small Positive Characteristic" (with E. Kaltofen), Proceedings of First Intern. Symposium on Parallel Symbolic Computation (PASCO '94), Linz, Austria (Sept. 1994), Lecture Notes Series in Computing, 5, 225-233, World Scientific Publishing Company, Singapore (1994).

118. "Simple Multivariate Polynomial Multiplication", Journal of Symbolic Computation, 18, 183-186 (1994).

117. "Optimum Parallel Computations with Band Matrices" (with I. Sobze and A. Atinkpahoun), Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms, 649-658, ACM Press, New York, and SIAM Publications, Philadelphia (1994).

116. "New Techniques for Approximating Complex Polynomial Zeros", Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms, 260-270, ACM Press, New York, and SIAM Publications, Philadelphia (1994).

115. "Improved Parallel Solution of a Triangular Linear System", Computers & Math. (with Applications), 27, 11, 41-43 (1994).

114. “New Resultant Inequalities and Complex Polynomial Factorization", SIAM Journal on Computing 23, 5, 934-950 (1994).

113. "The NC-Equivalence of Planar Integer Linear Programming and Euclidean GCD" (with D. Shallcross and Yu Lin-Kriz), Proc. 34th Ann. IEEE Symp. on Foundations of Computer Science, 557-564, IEEE Computer Society Press (1993).

112. "Improved Parallel Computations with Toeplitz-like and Hankel-like Matrices" (with D. Bini), Linear Algebra and Its Applications, 188, 189, 3-29 (1993).

111. “Improved Parallel Polynomial Division" (with D. Bini), SIAM J. on Computing 22, 3, 617-627 (1993).

110. "A New Algorithm for the Symmetric Tridiagonal Eigenvalue Problem" (with J. Demmel), Journal of Complexity, 9, 387-405 (1993).

109. "Generalized Compact Multigrid" (with J. Reif), Computers & Math. (with Applications), 25, 9, 3-5 (1993).

108. "Decreasing the Displacement Rank of a Matrix", SIAM J. on Matrix Analysis, 14, 1, 118-121 (1993)

107. "Fast and Efficient Parallel Solution of Sparse Linear Systems" (with J. Reif), SIAM J. on Computing, 22, 6, 1227-1250 (1993).

106. "Concurrent Iterative Algorithm for Toeplitz-like Linear Systems", IEEE Trans. on Parallel and Distributed Systems, 4, 5, 592-600 (1993).

105. "A New Approach to Fast Polynomial Interpolation and Multipoint Evaluation" (with A. Sadikou, E. Landowne and O. Tiga), Computers & Math. (with Applications), 25, 9, 25-30 (1993).

104. "Binary Segmentation for Matrix and Vector Operations", Computers & Math. (with Applications), 25,3, 69-71 (1993).

103. "Improved Parallel Polynomial Division and Its Extension" (with D. Bini), Proc. of 33rd Ann. IEEE Symp. on Foundations of Computer Science, 131-136, IEEE Computer Society Press (1992).

102. "Processor-Efficient Parallel Solution of Linear Systems II. The Positive Characteristic and Singular Cases" (with E. Kaltofen), Proc. of 33rd Ann. IEEE Symp. on Foundations of Computer Science, 714-723, IEEE Computer Society Press (1992).

101. "The Power of Combining the Techniques of Algebraic and Numerical Computing: Improved Approximate Multipoint Polynomial Evaluation and Improved Multipole Algorithms" (with J. Reif and S. Tate), Proc. of 33rd Ann. IEEE Symp. on Foundations of Computer Science, 703-713, IEEE Computer Society Press

100. "Improved Parallel Computations with Toeplitz-like and Hankel-like Matrices" (with D. Bini), Proc. of Annual ACM-SIGSAM Symp. on Symbolic and Algebraic Algorithms (ISSAC `93), 193-200, ACM Press, New York(1993).

99. "New Resultant Inequalities and Complex Polynomial Factorization", Proc. 1st Israel Symp. on Theory of Computing and Systems (ISTCS `92), Springer Lecture Notes in Computer Science, 601, 122-136 (1992).

98. "Improving the Solution of the Symmetric Eigenvalue Problem and an Extension", Applied Mathematics Letters, 5, 6, 49-50 (1992).

97.                   "Polynomial Division with a Remainder by Means of Evaluation and Interpolation" (with E. Landowne and A. Sadikou), Information Processing Letters, 44, 149-153 (1992).

96. "Practical Improvement of the Divide-and-Conquer Eigenvalue Algorithms" (with D. Bini), Computing, 48, 109-123 (1992).

95. "On Practical Algorithms for Accelerated Matrix Multiplication" (with J. Laderman and H.X. Sha), Linear Algebra and Its Applications, 162-164, 557-588 (1992).

94. "A Fast, Preconditioned Conjugate Gradient Toeplitz Solver" (with R. Schreiber), Computers & Math. (with Applications), 24, 7, 17-24 (1992).

93. "Parallel Solution of Toeplitz-like Linear Systems", J. of Complexity, 8, 1-21 (1992).

92. "Compact Multigrid" (with J. Reif), SIAM J. on Scientific and Statistical Computing, 13, 1, 119-127 (1992).

91. "Supereffective Slow-down of Parallel Computations" (with F.P. Preparata), Proc. 4th Ann. ACM Symp. on Parallel Algorithms and Architectures, 402-409, ACM Press, New York  (1992).

90. "Efficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs" (with Y. Han and J. Reif), Proc. 4th Ann. ACM Symp. on Parallel Algorithms and Architectures, 353-362, ACM Press, New York  (1992). 

89. "On Parallel Complexity of Integer Linear Programming, GCD and the Iterated Mod Function" (with Yu Lin-Kriz), Proc. 3rd Ann. ACM-SIAM Symposium on Discrete Algorithms, 124-137, ACM Press, New York and SIAM Publications, Philadelphia (1992).

88. "Parametrization of Newton's Iteration for Computations with Structured Matrices and Applications", Computers and Mathematics (with Applications), 24, 3, 61-75 (1992).

87. "Extended Concept of Significant Digits and Lower Precision Computations", Applied Mathematics Letters, 5, 2, 3-6 (1992).

86. "Univariate Polynomial Division with a Remainder by Means of Evaluation and Interpolation" (with E. Landowne and A. Sadikou), Proc. of 3rd IEEE Symp. on Parallel and Distributed Processing, 212-217, IEEE Computer Society Press (1991).

85. "The Parallel Computation of the Minimum Cost Paths in Graphs by Stream Contraction" (with J. Reif), Information Processing Letters, 40, 79-83 (1991).

84. "On the Evaluation of the Eigenvalues of a Banded Toeplitz Block Matrix" (with D. Bini), J. of Complexity, 7, 408-424 (1991).

83. "An Improved Newton Iteration for the Generalized Inverse of a Matrix, with Applications" (with R. Schreiber), SIAM J. on Scientific and Statistical Computing, 12, 5, 1109-1131 (1991).

82. "Processor Efficient Parallel Solution of Linear Systems over an Abstract Field" (with E. Kaltofen), Proc. 3rd Ann. ACM Symp. on Parallel Algorithms and Architectures, 180-191, ACM Press, New York  (1991).

81. "Improved Parallel Computations with Matrices and Polynomials" (with D. Bini and L. Gemignani), Proc. 18th Intern. Colloquium on Automata, Languages and Programming (ICALP '91), Lecture Notes in Computer Science, 510, 520-531, Springer (1991).

80. "Parallel Complexity of Tridiagonal Symmetric Eigenvalue Problem" (with D. Bini), Proc. 2nd Ann. ACM-SIAM Symp. on Discrete Algorithms, 384-393, ACM Press, New York, and SIAM Publications, Philadelphia (1991).

79. "The Modified Barrier Function Method for Linear Programming and Its Extensions" Computers & Math. (with Applications), 20, 3, 1-14 (1990).

78. "Estimating the Extremal Eigenvalues of a Symmetric Matrix", Computers & Math. (with Applications), 20, 2, 17-22 (1990).

77.                   “The Bit-Complexity of the Discrete Solution of PDEs: Compact Multigrid" (with J. Reif), Computers & Math. (with Applications), 20, 2, 9-16 (1990).



76. "On Computations with Dense Structured Matrices", Math. of Computation, 55, 191, 179-190 (1990).

75. "Parallel Polynomial Computations by Recursive Processes" (with D. Bini), Proc. ACM Symp. on Symb. & Alg. Comp., 294 (ISSAC-90), ACM Press, New York (1990).

74. "Parallel Least-Squares Solution of General and Toeplitz-like Linear Systems", Proc. 2nd Ann. ACM Symp. on Parallel Algorithms & Architecture, 244-253, ACM Press, New York (1990).

73. "On the Bit-Complexity of Discrete Solution of PDEs: Compact Multigrid" (with J. Reif), Proc. 17th International Colloquium on Automata, Languages and Programming (ICALP `90), Springer's Lecture Notes in Computer Science, 443, 612-625 (1990).

72. "Fast and Efficient Parallel Inversion of Toeplitz and Block Toeplitz Matrices", Operator Theory: Advances and Applications, 40, 359-389, Birkhaueser Verlag, Basel, Switzerland (1989).

71. "On Some Computations with Dense Structured Matrices", Proc. ACM-SIGSAM Internat. Symp. on Symbolic and Algebraic Computing, 34-42, ACM Press, New York (1989).

70. "Fast Evaluation and Interpolation at the Chebyshev Sets of Points" Applied Math. Letters, 2, 3, 255-258 (1989).

69. "Fast and Efficient Parallel Solution of Dense Linear Systems" (with J. Reif), Computers & Math (with Applications), 17, 11, 1481-1491 (1989).

68. "Fast and Efficient Parallel Evaluation of the Zeros of a Polynomial Having Only Real Zeros", Computers & Mathematics (with Applications), 17, 11, 1475-1480 (1989).

67. "Parallel Evaluation of the Determinant and of the Inverse of a Matrix" (with Z. Galil), Inform. Proc. Letters, 30, 41-45 (1989).

66. "Fast and Efficient Solution of Path Algebra Problems" (with J. Reif), Journal of Computer and Systems Sciences, 38, 3, 494-510 (1989).

65. "Computing the Determinant and the Characteristic Polynomial of a Matrix via Solving Linear Systems of Equations", Inform. Proc. Letters, 28, 2, 71-75 (1988).

64. "Efficient Algorithms for the Evaluation of the Eigenvalues of (Block) Banded Toeplitz Matrices" (with D. Bini), Mathematics of Computation, 50, 182, 431-448 (1988).

63. "Improved Processor Bounds for Combinatorial Problems in RNC" (with Z. Galil), Combinatorica, 8,2, 189-200 (1988).

62. "Some Polynomial and Toeplitz Matrix Computations" (with J. Reif), Proc. 28th Ann. IEEE Symp. on Foundations of Computer Science, 173-184, IEEE Computer Society Press (1987).

61. "Sequential and Parallel Complexity of Approximate Evaluation of Polynomial Zeros", Computers and Mathematics (with Applications), 14, 8, 591-622 (1987).

60. "Complexity of Parallel Matrix Computations", Theoretical Computer Science, 54, 65-85 (1987).
59. "Algebraic Complexity of Computing Polynomial Zeros", Computers & Math (with Applications), 14, 4, 285-304 (1987).

58. "A Logarithmic Boolean Time Algorithm for Parallel Polynomial Division" (with D. Bini), VLSI Algorithms and Architectures, Lecture Notes in Computer Science, 227, 246-251, Springer Verlag (1986), and Inform. Proc. Letters 24, 233‑237 (1987).

57. "Efficient Parallel Linear Programming" (with J. Reif), Operations Research Letters, 5,3, 127‑135 (1986).

56. "Parallel Nested Dissection for Path Algebra Computations" (with J. Reif), Operations Research Letters, 5,4, 177‑184 (1986).

55. "Fast and Efficient Linear Programming and Linear Least-Squares Computations" (with J. Reif), Computers and Mathematics (with Applications), 12A,12, 1217-1227 (1986).

54. "Extension of the Parallel Nested Dissection Algorithm to the Path Algebra Problems" (with J. Reif), Proc. Sixth Conference on Foundations of Software Technology and Theoretical Computer Science (New Delhi, India), Lecture Notes in Computer Science, 241, 470-487, Springer Verlag (1986).

53. "Fast Parallel Algorithms for Polynomial Division over Arbitrary Field of Constants" (with D. Bini), Computers and Mathematics (with Applications), 12A,11, 1105‑1118 (1986).

52. "Polynomial Division and Its Computational Complexity" (with D. Bini), Journal of Complexity, 2, 179‑203 (1986).

51. "A Logarithmic Boolean Time Algorithm for Parrallel Polynomial Division" (by D. Bini and V.Y. Pan), VLSI Algorithms and Architectures, Lecture Notes in Computer Science, 227, 246-251, Springer Verlag (Berlin)(1986).

50. "Fast and Efficient Parallel Linear Programming and Least Squares Computations" (with J. Reif), VLSI Algorithms and Architectures, Lecture Notes in Computer Science, 227, Springer‑Verlag, 283‑295 (1986).

49. "The Trade-off Between the Additive Complexity and Asynchronicity of Linear and Bilinear Algorithms", Information Processing Letters, 22, 11‑14 (1986).

48. "Algorithms for Polynomial Division" (with D. Bini), Proc. European Conference on Computer Algebra, Linz, Austria, Lecture Notes in Computer Science, 204, 1‑3, Springer Verlag (1985).

47. "Fast and Efficient Parallel Algorithms for the Exact Inversion of Integer Matrices", Proc. Fifth Conf. on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, 206, 504-521, Springer Verlag (1985).

46. "Fast and Efficient Algorithms for Sequential and Parallel Evaluation of Polynomial Zeros and of Matrix Polynomials," Proc. 26th Ann. IEEE Symp. on Foundations of Computer Sci., 522‑531, IEEE Computer Society Press (1985).

45. "Improved Processor Bounds for Algebraic and Combinatorial Problems in RNC" (with Z. Galil), Proc. 26th Ann. IEEE Symp. on Foundations of Computer Sci., 490‑495, IEEE Computer Society Press (1985).

44. "Efficient Parallel Solution of Linear Systems" (with J. Reif), Proc. 17th Ann. ACM Symp. on Theory of Computing, 143-152, ACM Press, New York (1985).

43. "On the Complexity of a Pivot Step of the Revised Simplex Algorithm", Computers & Math. (with Applications), 11,11, 1127-1140 (1985).

42. "Fast Parallel Polynomial Division via Reduction to Polynomial Inversion Modulo a Power" (with D. Bini), Information Processing Letters, 21, 79‑81 (1985).

41. "On Application of Some Recent Techniques of the Design of Algebraic Algorithms to the Sequential and Parallel Evaluation of the Roots of a Polynomial and to Some Other Numerical Problems", Computers & Math. (with Applications), 11,9, 911‑917 (1985).

40. "The Bit‑Complexity of Matrix Multiplication and of the Related Computations in Linear Algebra. The Segmented ‑algorithms", Computers & Math. (with Applications), 11,9, 919‑928 (1985).

39. "Fast Finite Methods for a System of Linear Inequalities", Computers & Math. (with Applications), 11,4, 355‑394 (1985).

38. "How Fast Can We Solve a System of Linear Inequalities in the Worst and in the Average Case?", Methods of Operations Research, 51, 107‑118 (1984).

37. "Trilinear Aggregating and the Recent Progress in the Asymptotic Acceleration of Matrix Operations", Theoretical Computer Science, 33, 117‑138 (1984).

36. "Trilinear Aggregating is the Basis for the Asymptotically Fastest Known Algorithms for Matrix Multiplication" (extended abstract), Methods of Operations Research, 45, 493‑494 (1983).

35. "The Projective Power Method for the Algebraic Eigenvalue Problem", Computers & Math. (with Applications), 9,6, 735‑745 (1983).

34. "The Additive and Logical Complexities of Linear and Bilinear Algorithms", J. of Algorithms, 4, 1‑34 (1983).

33. "Trilinear Aggregating is the Basis for the Asymptotically Fastest Known Algorithms for Matrix Multiplication", Conference Record, Second Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 321‑337, Bangalore, India (December 1982).

32. "Fast Matrix Multiplication without APA-Algorithms", Computers & Math. (with Applications), 8,5, 343‑366 (1982).

31. "The Bit‑Operation Complexity of Approximate Evaluation of Matrix and Polynomial Products Using Modular Arithmetic", Computers and Math. (with Applications), 8,2, 137‑140 (1982).

30. "Trilinear Aggregating with Implicit Canceling for a New Acceleration of Matrix Multiplication", Computers & Math. (with Applications), 8,1, 23-34 (1982).

29. "The Lower Bounds on the Additive Complexity of Bilinear Problems in Terms of Some Algebraic Quantities", Information Processing Letters, 13,2, 71‑72 (1981).

28. "The Bit‑Operation Complexity of Matrix Multiplication and of All Pair Shortest Path Problem", Computers & Math. (with Applications), 7, 5, 431‑438 (1981).

27. "A Unified Approach to the Analysis of Bilinear Algorithms", Journal of Algorithms, 2, 301‑310 (1981).

26. "The Bit‑Complexity of Arithmetic Algorithms", Journal of Algorithms, 2, 144-163 (1981).

25. "New Combinations of Methods for the Acceleration of Matrix Multiplications", Computers & Mathematics (with Applications), 7, 73‑125 (1981).

24. "Convolution of Vectors Over the Real Field of Constants", Journal of Algorithms, 1, 297‑300 (1980).

23. "New Fast Algorithms for Matrix Operations", SlAM J. on Computing, 9,2, 321‑342 (1980).

22. "Methods of Aggregations" (with W.L. Miranker), Linear Algebra and Its Applications, 29, 231‑257 (1980).

21. "Fields Extension and Trilinear Aggregating, Uniting and Canceling for the Acceleration of Matrix Multiplication", Proceedings of the 20th Annual IEEE Symposium on Foundations of Computer Science, 28‑38, IEEE Computer Society Press (1979).

20. "Strassen's Algorithm Is Not Optimal. Trilinear Technique of Aggregating, Uniting and Canceling for Constructing Fast Algorithms for Matrix Multiplication", Proceedings of the 19th Annual IEEE Symposium on Foundations of Computer Science, 166‑176, IEEE Computer Society Press (1978).

19. "Computational Complexity of Computing Polynomials over the Fields of Real and Complex Numbers", Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pp. 162-172, ACM Press, New York

18. "A Modification of a Balanced Model of Income-Commodities into an Equilibrium Model", (with V. Belkin, V. Ivanter, N. Konstantinov); Ekonomika I Matematicheskie Methody, Akademiya Nauk SSSR, 11,6, 1037-1049 (1975).

17. "A Model for the Dynamics of Costs and Expenditures", Trudy Mezhdunarodnoy Konferentsii "Modelirovanie Ekonomicheskikh Protsessov". (Transactions of the International Conference, "Models of Economic Processes"), Erevan, 166-174 (1974).

16. "A Model for the Optimization of Foreign Economic Relations Under the Economic Integration of the Socialist Countries", Ekonomika I Matematicheskie Metody, Akademiya Nauk SSSR, 10,2, 255-266 (1974). (Transl. USSR Trade and Services, 755, 1‑16 (1974).)

15. "Models for Planning Costs with Optimization of Foreign Trade of Several Countries under the Economic Integration", Primenenie Ekonomiko-Matematicheskikh Modeley I EVM pri Planirovanii I Prognozirovanii Tsen, 5 (1973).

14. "On Schemes for the Evaluation of Products and Inverses of Matrices", Uspekhi Matematicheskikh Nauk, 27,5 (167), 249-250 (1972).

13. "On Solving a Distribution Problem with Upper Limits on the Variables and with a Simplified Criterion Occurring in the Linear Problem of Optimizing Foreign Trade", Trudy 4-oy Zimney Schkoly po Matematicheskomu Programmirovaniyu I Smezhnym Voprosam. (Transactions of the 4-th Winter School on Mathematical Programming and Adjacent Problems, edited by S.I. Zukhovitskiy, Iss. 5, 26-49, Drogobych (1972).)

12. "A Linear Model and Algorithm for Optimizing Foreign Trade", Tezisy Dokladov I Vystupleniy na Simpoziume po Modelirovaniyu Narodnogo Khozyaistva, Institut Ekonomiki AN SSSR. (Proceedings of the Symposium on Models of Public Economy, Institute of Economics, Academy of Sciences of USSR, Moscow, 29-37 (1970).)

11. "Calculus of Rational Costs Based on Modern Economic Information", (with V. Belkin, A. Kronrod, Yu. Nazarov), Ekonomika I Matematicheskie Metody, Akademiya Nauk SSSR, 1,5, 699-717 (1965).

10. "On Methods of Computing the Values of Polynomials", Uspekhi Matematicheskikh Nauk, 21,1 (127), 103-134 (1966). (Transl. Russian Mathematical Surveys, 21,1 (127), 105-137 (1966).)

9. "On Simultaneous Evaluation of Several Polynomials of Low Degree (Two to Five)", Zhurnal Vychislitel'noy Matematiki I Matematicheskoy Fiziki, 6,2, 352-357 (1966). (Transl. USSR Computational Mathematics and Mathematical Physics, 6,2, 222-227 (1966).)

8. "The Evaluation of Polynomials of the Fifth and Seventh Degrees with Real Coefficients", Zhurnal Vychislitel'noy Matematiki I Matematicheskoy Fiziki, 5,1, 116‑118 (1965). (Transl. USSR Computational Mathematics and Mathematical Physics, 5,1, 159‑161 (1965).)

7. "Methods for Computing Polynomials", Ph.D. thesis, Dept. of Mechanics and Mathematics, Moscow State University (1964).

6. "Schemes with Preconditioning for the Evaluation of Polynomials and a Program for Automatic Preconditioning", Zhurnal Vychislitel'noy Matematiki I Matematicheskoy Fiziki, 2,1, 133-140 (1962). (Transl. USSR Computational Mathematics and Mathematical Physics,1, 137-146 (1963).).

5. "On Some Methods of Computing Polynomial Values", Problemy Kibernetiki, 7, 21-30 (1962). (Transl. Problems of Cybernetics, edited by A.A. Lyapunov, USSR, 7, 20-30, U.S. Dept. of Commerce (1962).)

4. "Some Schemes for the Evaluation of Polynomials with Real Coefficients", Problemy Kibernetiki, 5, 17-29 (1961). (Transl. Problems of Cybernetics, edited by A.A. Lyapunov, USSR, 5, 14‑32, Pergamon Press (1961).)

3. "On Approximation of Analytical Functions by Rational Ones", Uspekhi Matematicheskikh Nauk, 16,5 (101), 195-197 (1961).

2. "Some Schemes for the Evaluation of Polynomials with Real Coefficients", Doklady Akademii Nauk SSSR, 127,2, 266-269 (1959).

1. "On One Question by N.N. Luzin", Nauchnye Doklady Vysschey Schkoly, Phiziko-matematicheskie Nauki, 4, 59-6 (1958).

Reports and Manuscripts

5. “Inversion of Displacement Operators”, (with X. Wang), Preliminary Report, (2001).

4. “A Unified Superfast Divide-and-Conquer Algorithm for Structured Matrices”, MSRI Preprint 1999-033, Mathematical Sciences Research Institute, Berkeley, California (1999).

3. “Computations with Structured Matrices”, (with B. Murphy and R. Rosholt), MSRI  Preprint 1999-021, Mathematical Sciences Research Institute, Berkeley, California (1999).

2. "New Deterministic Parallel Algorithms for the Characteristic Polynomial of a Matrix over Abstract Fields", MSRI Preprint 1999-011, Mathematical Sciences Research Institute, Berkeley, California (1999).

1. "The Complexity of the Algebraic Eigenproblem" (with Z. Chen and A. Zheng), MSRI Preprint 1998-71, Mathematical Sciences Research Institute, Berkeley, California (1998).