From:	IN%"struse@mfdd5.cims.nyu.edu" 29-SEP-1994 11:35:48.41To:	IN%"vpan%lcvax.BITNET@uccvm.nyu.EDU"CC:	Subj:	Return-path: <struse@MFDD5.CIMS.NYU.EDU>Received: from UCCVM.NYU.EDU (MAILER@NYUCCVM) by lcvax.lehman.cuny.edu (PMDF #12809) id <01HHOLNH31HS000CVO@lcvax.lehman.cuny.edu>; Thu, 29 Sep 1994 11:35 ESTReceived: from NYUCCVM (NJE origin SMTP@NYUCCVM) by UCCVM.NYU.EDU (LMail V1.2a/1.8a) with BSMTP id 0042; Thu, 29 Sep 1994 11:29:33 -0400Received: from mfdd5.cims.nyu.edu by UCCVM.NYU.EDU (IBM VM SMTP V2R2) with TCP; Thu, 29 Sep 94 11:29:31 EDTReceived: by mfdd5.cims.nyu.edu (5.61/1.34) id AA09476; Thu, 29 Sep 94 11:28:27 -0400Date: Thu, 29 Sep 94 11:28:27 -0400From: struse@mfdd5.cims.nyu.edu (Pat Struse)To: vpan%lcvax.BITNET@uccvm.nyu.EDUMessage-id: <9409291528.AA09476@mfdd5.cims.nyu.edu>Your paper with P94\documentstyle [11pt] {article}\topmargin-.25in\oddsidemargin.05in\evensidemargin.05in\textheight8.55in\textwidth6in\renewcommand{\baselinestretch}{1.5}\begin{document}\begin{center}{\bf Parallel Computation of a KrylovMatrix for a Sparse and Structured Input}\footnote{Supported by NSF Grant CCR 9020690and PSC CUNY Awards Nos. 662478 and 664334.}\end{center} \begin{center}{\bf  Victor~Y.~Pan \\Department of Mathematics and Computer Science\\ Lehman College, City University of New York\\ Bronx, NY 10468 \\Internet:  VPAN@LCVAX.BITNET}\end{center}\thispagestyle{empty}\vspace*{.5in} \begin{abstract}As in our previous work, we reduce parallel computation of a Krylov matrix tosolving a parametrized linear system of equations. This time we show that sucha method is effective in the cases of banded matrices, sparse andstructured matrices and triangular matrices.\end{abstract}\vspace{.3in} \noindent{\bf Key Words:} Krylov sequences, Krylov matrices, linear systems,band matrices, sparse matrices, triangular matrices.\vspace{.3in} \noindent{\bf AMS 1991 Math. Subject Classification:} 65F50, 65F15, 65F05.\newpageFor a pair of natural $m$ and $n$, an $n\times n$ matrix $A$, and an$n$-dimensional vector $v$, one may define the $n \times m$ Krylovmatrix$$K(A,v,m) = (v,Av,A^2 v,A^3 v, \ldots , A^{m-1} v) \ , \eqno (1)$$whose computation (for various $m$ ranging from a small constant to orderof $n$) is a major task of numerical linear algebra, [GL]. Sequentialcomputation of $K(A,v,m)$ is straightforward: it amounts to $m-1$ successivemultiplications of the matrix $A$ by vectors $A^i v$, $i=0,1,\ldots ,m-2$. To evaluate the matrix $K(A,v,m)$ on a parallel computer (assuming $m=2^h -1$ for simplicity)one may recursively compute the matrices $A^{2^i}$,$i=1,\ldots ,h-1$, and then$$A^2 (v,Av) = (A^2 v,A^3 v) \ ,$$$$A^4 (v,Av,A^2 v,A^3 v)=(A^4 v,A^5 v,A^6 v,A^7 v) \ , \eqno (2)$$$$\ .  \ .  \ .  \ .  \ .  \ .  \ .  \ .  \ .  \ .  \ .  \ .  \ .  \ .  \ .\ .  \ .  \ .  \ .  \ .  \ .  \ .  \ .  \ .  \ .  \ .  \ .  \ .  \ .  \ .$$This well-known algorithm [BP] only needs $2h-2$ matrix multiplications,which, however, do not preserve the structure of $A$. For structured (denseand sparse) matrices $A$, we will recall the distinct approach of [P92],originally proposed for Toeplitz and Toeplitz-like matrices $A$, and willextend it to the cases of banded (block tridiagonal) and some other specialmatrices $A$. According to the recipe of [P92], one should introduce an auxiliary scalarparameter $\lambda$, define the matrix $B(\lambda )=I-\lambda A$, and thencompute the column vectors $A^i v$ of $K(A,v,m)$ as the coefficients ofNewman's expansion,$$B(\lambda )^{-1} v=(I-\lambda A)^{-1} v=\sum_{i=0}^{\infty} (\lambda A)^iv \ ,$$reduced modulo $\lambda^m$. Due to the latter equation, the computation of the Krylov matrix $A$ of(1) reduces to the solution of the linear system$$B(\lambda )x=v \ {\rm mod} \ \lambda^m \ . \eqno (3)$$Our task respectivelyreduces to recalling some parallel algorithms for the system (3),for some selected classes of matrices $A$, and to estimating parallelarithmetic cost of performing these algorithms(in terms of parallel time and the number of processors used), andwe will refer the reader to the relevantbibliography for the proofs and details. To express this parallel cost, we hereafter let $O(t,p)$ denote thepair of simultaneous bounds $O(t)$ on the arithmetic parallel time and$O(p)$ on the number of processors supporting this time bound. Under thisnotation, $O(\log k,k)$ bounds the parallel cost of addition, subtractionand multiplication of a pair of polynomials in $\lambda$ performedmodulo $\lambda^k$ [BP]; furthermore, essentially the same cost boundsapply to computation modulo $\lambda^k$ of the reciprocal of a polynomialin $\lambda$ with a nonzero $\lambda$-free term. Hereafter, we let $O(t_{I(k)} ,p_{I(k)} )$ denote the parallel complexityof $k\times k$ matrix inversion, where we may set $t_{I(k)} =\log^2 k$,$p_{I(k)} =k^d /\log k$, [BP], assumed randomization and provided that$k\times k$ matrix multiplication costs $O(\log k,k^d /\log k)$.(Theoretically, one may set $d < 2.38$, but practically $d$ stays at thelevels 3 or 2.81, [GL], [BP].) We note thatthe  algorithm (2) computes the Krylov matrix$K(A,v,m)$ at the cost $O((\log m)\log n,n^d )$ for a general (dense andunstructured) matrix $A$. Next we will show improved estimates in the caseof special matrices $A$. In particular, the latter bound decreases to $O((\log m)\log n,mn/\log m)$if $A$ is a {\it Toeplitz or Hankel matrix} or, more generally, a{\it Toeplitz-like} + {\it Hankel-like matrix}, [P92], [BP93], [BP]. Next consider the cost of $s \times s$ {\it block tridiagonal matrices}$A$ with $k\times k$ blocks, which is essentially the case of {\it bandedmatrices} $A$. Thenwe may solve the system (3) by applying the block cyclic reductionalgorithm [GL]. The cost of application of this algorithm to the scalarinput matrix is bounded by$$O(t_{I(k)} \log s, p_{I(k)} s/\log s)$$(see [PSA]). Since we deal with polynomials reduced modulo $\lambda^m $,the cost of every arithmetic operation increases from $O(1,1)$ to$O(\log m,m)$, and we arrive at the overall cost $O((\log m)t_{I(k)}\log s, mp_{I(k)} s/\log s)$. Next consider the case of {\it sparse matrices} $A$ given with {\it their}$s(n)$-{\it separator families}, $s(n) = o(n)$, (see definitions of[LRT], [GT], [P93], [PR]). In this case application of the parallelgeneralized nested dissection algorithm of [PR] gives the cost bound$O(\log^3 n,(s(n)^d )/\log^2 n)$ for solving a linear system with scalarsparse input matrix. This is immediately extended to the cost bound$O((\log m)\log^3 n,(s(n))^d m/\log^2 n)$ for the solution of the system(3). We conclude with the case of triangular matrices $A$.In this case we may applythe algorithm of [P94], [PP], which supports the cost bound $O( \sqrt{n}\log n,n^{3/2} /\log n)$ for solving a triangular linear system with ascalar coefficient matrix. For the system (3) this cost bound turns into$O((\log m) \sqrt{n} \log n,n^{3/2} m/\log n)$. Compared to the cost bound$O(n \log n,n^2 /\log n)$ of the straightforward evaluation of $K(A,v,m)$via $m-1$ successive multiplications of $A$ by vectors, we note accelerationif $\sqrt{n} \log n= o(m)$.\newpage\begin{center}{\bf REFERENCES}\end{center} \begin{description}\item [BP93]D. Bini, V.Y. Pan, Improved Parallel Computation with Toeplitz-likeand Hankel-like Matrices, {\it Linear Algebra and Its Applications},188, 189, 3-29, 1993.\item [BP]D. Bini, V.Y. Pan, {\it Polynomial and Matrix Computations: v. 1,Fundamental Algorithms}, Birkhauser, Boston, 1994.\item [GL]G.H. Colub, C.F. Van Loan, {\it Matrix Computations}, Johns HopkinsUniversity Press, Baltimore, Maryland, 1989.\item [GT]J.R. Gilbert, R.E. Tarjan, The Analysis of Nested Dissection Algorithm,{\it Numer. Math.}, 50, 377-404, 1987.\item [LRT]R.J. Lipton, D. Rose, R.E. Tarjan, Generalized Nested Dissection, {\itSIAM J. on Numer. Analysis}, 16, 2, 346-358, 1979.\item [P93]V.Y. Pan, Parallel Solution of Sparse and Path Systems, in {\it Synthesis ofParallel Algorithms} (J.H. Reif, editor), Chapter 14, 621-678, MorganKaufmann, San Diego, California, 1993.\item [P92]V.Y. Pan, Parametrization of Newton's Iteration for Computations withStructured Matrices and Applications, {\it Computers \& Math. (withApplications)}, 24, 3, 61-75, 1992.\item [P94]V.Y. Pan, Improved Parallel Solution of a Triangular Linear System,{\it Computers \& Math. (with Applications)}, 27, 11, 41-43, 1994.\item [PP]V.Y. Pan, F.P. Preparata, Work-Preserving Speed-up of Parallel MatrixComputations, {\it SIAM J. on Computing}, 24, 4, 1995.\item [PR]V.Y. Pan, J.H. Reif, Fast and Efficient Solution of Sparse Linear Systems,{\it SIAM J. on Computing}, 22, 6, 1227-1250, 1993.\item [PSA]V.Y. Pan, I. Sobze, A. Atinkpahoun, On Parallel Computation with BandMatrices, {\it Information and Computation}, to appear.\end{description}\end{document}