------------------------------------------------------------------------------

                                       
		     B O S T O N   U N I V E R S I T Y
                                       
			Computer Science Department
                                       
			    C O L L O Q U I U M
                                       
			 Friday, November 15, 1996
                                       
				  1:30 pm
                                       
		 (Coffee served at 1:00 pm, Room MCS 137)

			       Room MCS 135

------------------------------------------------------------------------------

		    POLYNOMIAL AND MATRIX COMPUTATIONS

				Victor Pan
			      Lehman College
			City University of New York
		      250 Bedford Park Boulevard West
			Bronx, New York 10468-1589


  One of the major topics of our recent book [B-P] was the study of
  computations with Toeplitz and other dense structured matrices considered
  as a link between computations with polynomials and with general
  matrices. This study has lead us to improving computations in both of the
  latter areas and to narrowing the gap historically arisen between them. In
  the talk we recall some examples of correlations between Toeplitz matrices
  and general matrices and between Toeplitz matrices and polynomials, which
  enabled us to improve parallel algorithms for some fundamental computations
  in all 3 areas.  For some major computations with $n \times n$ Toeplitz and
  Toeplitz-like matrices $A$ (rank, inverse, linear system solving), we have
  obtained the parallel complexity bounds
  
    a) of $O(\log^2 n)$ time and $O(n^2/\log n)$ arithmetic processors over
  any field of characteristic zero or greater than $n$ (recalled from [B-P]),
    b) of $O(\log^3 n)$ and $O(n^2/\log^2 n)$, respectively, over any field
  [P1], and
    c) of $O((\log n) \log (n\log \|A\|))$ and $O(n \log n)$, respectively,
  over the integers [B-P], [P2].
  
  The two latter results, of b) and c), over any field and integers, are
  randomized, and our computations over the integers (part c)) only involve
  $O(n \log \|A\|)$-bit precision.
  
    [B-P] D. Bini, V. Y. Pan, Polynomial and Matrix Computations, vol. 1,
  Birkhauser, Boston, 1994.
    [P1] V. Y. Pan, Parallel Computations of Polynomial GCD and Related
  Computations, Proc. Seventh Ann. ACM-SIAM Symp.  on Discrete Algorithms,
  January 1996.
    [P2] V. Y. Pan, Effective Parallel Computations with Toeplitz and
  Toeplitz-like Matrices Filled with Integers, preprint.

Host: Prof. Leonid Levin

------------------------------------------------------------------------------
For colloquium info, including directions, see http://www.cs.bu.edu/colloquium
     For more information contact Prof. David Yates <djy@cs.bu.edu>
------------------------------------------------------------------------------