Univariate polynomial root-finding has been studied for four millennia and very intensively in the last decades. Our novel nearly optimal Las Vegas randomized root-finders approximate all zeros of a polynomial almost as fast as one accesses its coefficients with the precision required for the solution within a prescribed error bound.1 Moreover, our root-finders can be applied to a black box polynomial, defined by an oracle (that is, black box subroutine) for its evaluation rather than by its coefficients. Such root-finders are particularly fast for polynomials that can be evaluated fast, e.g., the sum of a few shifted monomials, but the only other known black box root-finder is the pioneering one by Louis and Vempala at FOCS 2016, and it only approximates the absolutely largest root of a real-rooted polynomial. Our deterministic divide and conquer algorithm of ACM STOC 1995 is the only other known nearly optimal polynomial root-finder, and it extensively uses the coefficients, is quite involved, and has never been implemented, while according to extensive numerical experiments with standard test polynomials, already initial implementations of our new root-finders compete with user's choice package of root-finding subroutine MPSolve and supersede it more and more significantly where the degree of a polynomial grows large. Our root-finders are readily extended to support approximation of the eigenvalues of a matrix within a record Las Vegas expected bit operation time bound. Our auxiliary algorithms and techniques for computations with black box polynomials can be of independent interest.

The recent advanced sub-division algorithm is nearly optimal for the approximation of the roots of a dense polynomial given in monomial basis; moreover, it works locally and slightly outperforms the user's choice MPSolve when the initial region of interest contains a small number of roots. Its basic and bottleneck block is counting the roots in a given disc on the complex plain based on Pellet's theorem, which requires the coefficients of the polynomial and expensive shift of the variable. We implement a novel method for both root-counting and exclusion test, which is faster, avoids the above requirements, and remains efficient for sparse input polynomials. It relies on approximation of the power sums of the roots lying in the disc rather than on Pellet's theorem. Such approximation was used by Schönhage in 1982 for the different task of deflation of a factor of a polynomial provided that the boundary circle of the disc is sufficiently well isolated from the roots. We implement a faster version of root-counting and exclusion test where we do not verify isolation and significantly improve performance of subdivision algorithms, particularly strongly in the case of sparse inputs. We present our implementation as heuristic and cite some relevant results on its formal support presented elsewhere.

We assume that a real square-free polynomial A has a degree d, a maximum coefficient bitsize τ and a real root lying in an isolating interval and having no nonreal roots nearby (we quantify this assumption). Then, we combine the Double Exponential Sieve algorithm (also called the Bisection of the Exponents), the bisection, and Newton iteration to decrease the width of this inclusion interval by a factor of t=2-L. The algorithm has Boolean complexity ÕB(d2 τ + d L ). Our algorithms support the same complexity bound for the refinement of r roots, for any r ≤ d.

MBA algorithm inverts a structured matrix in nearly linear arithmetic time but requires a serious restriction on the input class. We remove this restriction by means of randomization and extend the progress to some fundamental computations with polynomials, e.g., computing their GCDs and AGCDs, where most effective known algorithms rely on computations with matrices having Toeplitz-like structure. Furthermore, our randomized algorithms fix rank deficiency and ill conditioning of general and structured matrices. At the end we comment on a wide range of other natural extensions of our progress and underlying ideas.

Recent progress on root-finding for polynomial and secular equations largely relied on eigen-solving for the associated companion and diagonal plus rank-one generalized companion matrices. By applying to them Rayleigh quotient iteration, we could have already competed with the current best polynomial root-finders, but we achieve further speedup by applying additive preprocessing. Moreover our novel rational maps of the input matrix enables us to direct the iteration to approximating only real roots, so that we dramatically accelerate their numerical computation in the important case where they are much less numerous than all complex roots.

The celebrated LKS algorithm by Lehmer, Knuth, and Schönhage, combined with the product tree technique, enables an equivalently rapid alternative to our recent modification of the extended Euclidean algorithm for the reconstruction of a rational number from its modular as well as numerical approximations.

We propose new Las Vegas randomized algorithms for the solution of a square nondegenerate system of equations, with well-separated roots. The algorithms use $\Oc (\delta\, \csttn D^{2} \log(D) \log(b))$ arithmetic operations (in addition to the operations required to compute the normal form of the boundary monomials modulo the ideal) to approximate all real roots of the system as well as all roots lying in a fixed n-dimensional box or disc. Here D is an upper bound on the number of all complex roots of the system (e.g., Bezout or Bernshtein bound), $\delta$ is the number of real roots or the roots lying in the box or disc, and $\epsilon=2^{-b}$ is the required upper bound on the output errors. For computing the normal form modulo the ideal, the efficient practical algorithms of [B. Mourrain and P. Trébuchet, in Proceedings of the International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2000, pp. 231--238] or [J. C. Faugère, J. Pure Appl. Algebra, 139 (1999), pp. 61--88] can be applied. We also yield the bound $\Oc( \csttn D^{2} \log(D) )$ on the complexity of counting the numbers of all roots in a fixed box (disc) and all real roots. For a large class of inputs and typically in practical computations, the factor $\delta$ is much smaller than $D, \delta=o(D)$. This improves by the order of magnitude the known complexity estimates of the order of at least 3 n D 4 + D 3 log(b) or D 4 , which so far are the record estimates even for the approximation of a single root of a system and for each of the cited counting problems, respectively. Our progress relies on proposing several noveltechniques. In particular, we exploit the structure of matrices associated to a given polynomial system and relate it to the associated linear operators, dual space of linear forms, and normal forms of polynomials in the quotient algebra; furthermore, our techniques support the new nontrivial extension of the matrix sign and quadratic inverse power iterations to the case of multivariate polynomial systems, where we emulate the recursive splitting of a univariate polynomial into factors of smaller degree.

We accelerate the known algorithms for computing a selected entry of the extended Euclidean algorithm for integers and, consequently, for the modular and numerical rational number reconstruction problems. The acceleration is from quadratic to nearly linear time, matching the known complexity bound for the integer gcd, which our algorithm computes as a special case.

We accelerate the extended Euclidean algorithm for integers, the rational number reconstruction, and consequently, the stage of the recovery of the solution of a nonsingular integer system of linear equations via Hensel's lifting. The acceleration is by the order of magnitude and yields nearly optimal randomized algorithms. In the highly important case of Toeplitz, Hankel, and Toeplitz/Hankel-like linear systems, the accleration is potentially practical.

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 annulus on the complex plane, whereas another algorithm numerically splits the input polynomial of the n-th degree into two factors balanced in the degrees and with the zero sets separated by the basic annulus. Recursive combination of the two algorithms leads to recursive computation of the complete numerical factorization of a polynomial into the product of linear factors and further to the approximation of the roots. The new rootfinder incorporates the earlier techniques of Schönhage and Kirrinnis and our old and new techniques and yields nearly optimal (up to polylogarithmic factors) arithmetic and Boolean cost estimates for the complexity of both complete factorization and rootfinding. The improvement over our previous record Boolean complexity estimates is by roughly the factor of n for complete factorization and also for the approximation of well-conditioned (well isolated) roots, whereas the same algorithm is also optimal (under both arithmetic and Boolean models of computing) for the worst case input polynomial, where the roots can be ill-conditioned, forming clusters. (The worst case bounds are supported by our previous algorithms as well.) Al our algorithms allow processor efficient acceleration to achieve solution in polygarithmic parallel time.

The known fast sequential algorithms for multiplying two NxN matrices (over an arbitrary ring) have time complexity O(Nα), where 2α, multiplying two NxN matrices can be performed on a p-processor linear array with a reconfigurable pipelined bus system (LARPBS) in O(Nm/P+(N2/p2α/)log p) time. This is currently the fastest parallelization of the best known sequential matrix multiplication algorithm on a distributed memory parallel system. In particular, for all 12.3755, multiplying two NxN matrices can be performed on a p-processor LARPBS in O(N2.3755/p+(N2)/p0.8419log p) time and linear speedup can be achieved for p as large as O(N2.3755/(log N)6.3262). Furthermore, multiplying two NxN matrices can be performed on an LARPBS with O(Nα) processors in O(log N) time. This compares favorably with the performance on a PRAM.

We exploit various matrix structures to decrease the running time and memory space of the known practical deterministic schemes for erasure-resilient encoding/decoding. Polynomial interpolation and multipoint evaluation enable both encoding and decoding in nearly linear time but the overhead constants are large (particularly, for interpolation), and more straightforward quadratic time algorithms prevail in practice. We propose faster algorithms. At the encoding stage, we decrease the running time per information packet from C log2 r, for a large constant C, or from r (for practical encoding) to log r. For decoding, our improvement is by the factors C and N/log N, respectively, for the input of size N. Our computations do not involve polynomial interpolation. Multipoint polynomial evaluation is either also avoided or is confined to decoding.

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 computations includes, in particular, the evaluation of the greatest common divisor (gcd), the least common multiple (lcm), and the resultant of two polynomials, computing Padé approximation and the Berlekamp--Massey recurrence coefficients, as well as numerous problems reducible to these. Transition to Toeplitz and Toeplitz-like computations is currently the basis for the design of the parallel randomized NC (RNC) algorithms for these computational problems. Our main result is in constructing nearly optimal randomized parallel algorithms for Toeplitz and Toeplitz-like computations and, consequently, for numerous related computational problems (including the computational problems listed above), where all the input values are integers and all the output values are computed exactly. This includes randomized parallel algorithms for computing the rank, the determinant, and a basis for the null-space of an n × n Toeplitz or Toeplitz-like matrix A filled with integers, as well as a solution x to a linear system A x = f if the system is consistent. Our algorithms use O((log n) log (n log |A|)) parallel time and O(n log n) processors, each capable of performing (in unit time) an arithmetic operation, a comparision, or a rounding of a rational number to a closest integer. The cost bounds cover the cost of the verification of the correctness of the output. The computations by these algorithms can be performed with the precision of O(n log |A|) bits, which matches the precision required in order to represent the output, except for the rank computation, where the precision of the computation decreases. The algorithms involve either a single random parameter or at most 2n-1 parameters. The cited processor bounds are less by roughly factor n than ones supported by the known algorithmsthat run in polylogarithmic arithmetic time and do not use rounding to the closest integers. Technically, we first devise new algorithms supporting our old nearly optimal complexity estimates for parallel computations with general matrices filled with integers. Then we decrease dramatically, by roughly factor n 1.376 , the processor bounds required in these algorithms in the case where the input matrix is Toeplitz-like. Our algorithms exploit and combine some new techniques (which may be of independent interest, e.g., in the study of parallel and sequential computation of recursive factorization of integer matrices) as well as our earlier techniques of variable diagonal (relating to each other several known algebraic and numerical methods), stream contraction, and the truncation of displacement generators in Toeplitz-like computations; our development and application of these techniques may be of independent

The eigenproblem for an n-by-n matrix A is the problem of the approximation (within a relative error bound 2-') of all the eigenvalues of the matrix A and computing the associated eigenspaces of all these eigenvalues.We show that the arithmetic complexity of this problem is bounded by O(n3 + (nlog'n)log b).If the characteristic and mini-

The classical scalar Nevanlinna-Pick interpolation problem has a long and distinguished history, appearing in a variety of applications in mathematics and electrical engineering. There is a vast literature on this problem and on its various far reaching generalizations. It is widely known that the now classical algorithm for solving this problem proposed by Nevanlinna in 1929 can be seen as a way of computing the Cholesky factorization for the corresponding Pick matrix. Moreover; the classical Nevanlinna algorithm takes advantage of the special structure of the Pick matrix to compute this triangular factorization in only O(n/sup 2/) arithmetic operations, where n is the number of interpolation points, or equivalently, the size of the Pick matrix. Since the structure-ignoring standard Cholesky algorithm [though applicable to the wider class of general matrices] has much higher complexity O(n/sup 3/), the Nevanlinna algorithm is an example of what is now called fast algorithms. In this paper we use a divide-and-conquer approach to propose a new superfast O(n log/sup 3/ n) algorithm to construct solutions for the more general boundary tangential Nevanlinna-Pick problem. This dramatic speed-up is achieved via a new divide-and-conquer algorithm for factorization of rational matrix functions; this superfast algorithm seems to have a practical and theoretical significance itself. It can be used to solve similar rational interpolation problems [e.g., the matrix Nehari problem], and a variety, of engineering problems. It can also be used for inversion and triangular factorization of matrices with displacement structure, including Hankel-like, Vandermonde-like, and Cauchy-like matrices.

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, complicating the already difficult classical problem, is motivated by several practical applications. We first reduce the solution to the computation of the eigenvector of an associated matrix. Our novel treatment of this rather customary stage enables us to unify several known approaches and to simplify substantially the solution of an overconstrained polynomial system having only a simple root or a few roots. Likewise, when the reduction of a general polynomial system to an eigenproblem relies on the Gröbner basis techniques, we also obtain substantial simplification. Then we elaborate application of the power method and the (shifted) inverse power method to the solution of the resulting eigenproblem. Our elaboration is not straight-forward since we achieve the computation preserving the sparsity and the structure of the associated matrix involved. This enables the decrease of the arithmetic cost by roughly factor N , denoting the dimension of the associated resultant matrix. Furthermore, our experiments show that our computations can be performed numerically, with single or double precision arithmetic, and the iteration converged to the specified root quite fast.

Award 668365) We propose new Las Vegas randomized algorithms for the solution of a multivariate generic or sparse polynomial system of equations. The algorithms use O ( ( +4 n)3 nD2 log b) arithmetic operations to approximate all real roots of the system as well as all roots lying in a fixed n-dimensional box or disc. Here D is an upper bound on the number of all the roots of the system, is the number of real roots or the roots lying in the box or disc, =2;b is the required upper bound on the output errors, and O (s) stands for O(s log c s), c being a constant independent of s. We also yield the bounds O (12 nD2) for the complexity of counting the numbers of all roots in a fixed box (disc) and all real roots and O (12 nD2 log b) for the complete solution of generic system. For a large class

Surprisingly simple corollaries from the Courant--Fischer minimax characterization theorem enable us to devise a very effective algorithm for the evaluation of a set S interleaving the set E of the eigenvalues of an n X n real symmetric tridiagonal (rst) matrix T n (as well as a point that splits E into two subsets of comparable cardinalities). Furthermore, we extend this algorithm so as to approximate all the n eigenvalues of T n at nearly optimal sequential and parallel cost, that is, at the cost of staying within polylogarithmic factors from the straightforward lower bounds. The resulting improvement of the known processor bound in NC algorithms for the rst-eigenproblem is roughly by factor n. Our approach extends the previous works [M. Ben-Or and P. Tiwari, J. Complexity, 6(1990), pp. 417--442] and [M. Ben-Or et al., SIAM J. Comput., 17(1988), pp. 1081--1092] for the approximation of the zeros of a polynomial having only real zeros, and our algorithm leads to an alternative and simplified derivation of the known record parallel and sequential complexity estimates for the latter problem.

It is not known if planar integer linear programming is P-complete or if it is in NC, and the same can be said about the computation of the remainder sequence of the Euclidean algorithm applied to two integers. However, both computations are NC equivalent. The latter computational problem was reduced in NC to the former one by Deng [Mathematical Programming: Complexity and Application, Ph.D. dissertation, Stanford University, Stanford, CA, 1989; Proc. ACM Symp. on Parallel Algorithms and Architectures, 1989,pp. 110--116]. We now prove the converse NC-reduction.

International audience

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 algebra. Sparse elimination theory has introduced the sparse resultant, which takes into account the sparse structure of the polynomials. The construction of sparse resultant, or Newton, matrices is a critical step in the computation of the resultant and the solution of the system. We exploit the matrix structure and decrease the time complexity ofconstructing such matrices to roughly quadratic in the matrix dimension, whereas the previous methods had cubic complexity. The space complexity is also decreased by one order of magnitude. These results imply similar improvements in the complexity of computing the resultant itself and of solving zero-dimensional systems. We apply some novel techniques for determining the rank of rectangular matrices by an exact or numerical computation. Finally, we improve the existing complexity for polynomial multiplication under our model of sparseness, o ering bounds linear in the number of variables and the number of nonzero terms.

Article Free Access Share on Faster solution of the key equation for decoding BCH error-correcting codes Author: Victor Y. Pan Department of Mathematics and Computer Science, Lehman College, City University of New York, Bronx, NY Department of Mathematics and Computer Science, Lehman College, City University of New York, Bronx, NYView Profile Authors Info & Claims STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computingMay 1997 Pages 168–175https://doi.org/10.1145/258533.258577Online:04 May 1997Publication History 6citation791DownloadsMetricsTotal Citations6Total Downloads791Last 12 Months11Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Our new algorithmsfor approximating all the complex zeros of an n-th degree polynomial I}(:L ) save both Boolean and arithmetic sequential tim (', vcr-

Brent’s scheduling principle provides a general simulation scheme when fewer processors are available than specified by the fastest parallel algorithm. Such a scheme preserves, under slow-down, the actual number of executed operations, also called work. In this paper we take the complementary viewpoint, and rather than consider the work-preserving slow-down of some fast parallel algorithm, we investigate the problem of the achievable speedups of computation while preserving the work of the best-known sequential algorithm for the same problem. The proposed technique, eminently applicable to problems of matrix-computational flavor, achieves its result through the interplay of two algorithms with significantly different features. Analogous but structurally different “interplays” have been used previously to improve the algorithmic efficiency of graph computations, selection, and list ranking. We demonstrate the efficacy of our technique for the computation of path aigebras in graphs and digraphs and various fundamental computations in linear algebra. Some of the fundamental new algorithms may have practical value; for instance, we substantially improve the algorithmic performance of the parallel solution of triangular and Toeplitz linear systems of equations and the computation of the transitive closure of digraphs.

The author deduces some new probabilistic estimates on the distances between the zeros of a polynomial $P(x)$ by using some properties of the discriminant of $P(x)$ and applies these estimates to improve the fastest deterministic algorithm for approximating polynomial factorization over the complex field. Namely, given a natural n, positive $ \in $, such that $\log ({1 / \epsilon }) = O(n\log n)$, and the complex coefficients of a polynomial $P(x) = \sum _{i = 0}^n p_i x^i $, such that $p_n \ne 0$, $\sum _i |p_i | \leqslant 1$, a factorization of $p(x)$ (within the error norm $ \in $) is computed as a product of factors of degrees at most ${n / 2}$, by using $O(\log ^2 )$) time and $n^3 $ processors under the PRAM arithmetic model of parallel computing or by using $O(n^2 \log ^2 n)$ arithmetic operations. The algorithm is randomized, of Las Vegas type, allowing a failure with a probability at most $\delta < 1$, for any positive $\delta < 1$ such that $\log ({1 / \delta }) = O(\log n)$. Except for a narrow class of polynomials $p(x)$, these results can be also obtained for $ \epsilon $ such that $O(n^2 \log n)$.

We show NC-reduction of integer linear programming with two variables to the evaluation of the remainder sequence arising in the application of the Euclidean algorithm to two positive integers. Due to the previous result of X. Deng (1989), this implies NC-equivalence of both of these problems, whose membership in NC, as well as P-completeness, remain unresolved open problems.>

The authors compute the first N coefficients of the reciprocal $r(x)$, $r(x)p(x) = 1\bmod x^N $ (given a natural N and a polynomial $p(x)$), $(p(0) \ne 0)$, by using $O(h\log N)$ arithmetic steps and $O(({N / h})(1 + 2^{ - h} \log ^{(h)} N))$ processors, for any h, $h = 1,2, \ldots ,\log ^ * N$, under the PRAM arithmetic models, provided that $O(\log m)$ steps and m processors suffice to perform discrete Fourier transforms on m points and that $\log ^{(0)} N = N$, $\log ^{(h)} N = \log _2 \log ^{(h - 1)} N$, $h = 1, \ldots ,\log ^ * N$, $\log ^ * N = \max \{ {h:\log ^{(h)} N > 0} \}$. The same estimates apply to some other computations, such as the division with a remainder of two polynomials of degrees $O(N)$ and the inversion of an $N \times N$ triangular Toeplitz matrix. This improves the known estimates of Reif–Tate and Georgiev. The presented techniques are extended to parallel implementation of other recursive processes, such as the evaluation modulo $x^N $ of the mth root $p(x)^{{1 / m}} $ of $p(x)$ (for any fixed natural m), for which we need $O(\log N\log \log N)$ timesteps and $O({N / {\log \log N}})$ processors. The paper demonstrates some new techniques of supereffective slowdown of parallel algebraic computations combined with the technique of stream contraction.

This paper presents a parallel algorithm for the solution of a linear system $A{\bf x} = {\bf b}$ with a sparse $n \times n$ symmetric positive definite matrix A, associated with the graph $G(A)$ that has n vertices and has an edge for each nonzero entry of A. If $G(A)$ has an $s(n)$-separator family and a known $s(n)$-separator tree, then the algorithm requires only $O(\log ^3 n)$ time and $(|E| + {{M(s(n)))} / {\log n}}$ processors for the evaluation of the solution vector ${\bf x} = A^{ - 1} {\bf b}$, where $|E|$ is the number of edges in $G(A)$ and $M(n)$ is the number of processors sufficient for multiplying two $n \times n$ rational matrices in time $O(\log n)$. Furthermore, for this computational cost the algorithm computes a recursive factorization of A such that the solution of any other linear system $A{\bf x} = {\bf b}'$ with the same matrix A requires only $O(\log ^2 n)$ time and $({{|E|} / {\log n}}) + s(n)^2 $ processors.

A nonsingular n*n matrix A is given with its short displacement generator. It has small displacement rank bounded by a fixed constant. The class of such matrices generalizes Toeplitz matrices. A good initial approximation to a short displacement generator for A/sup -1/ is readily available. Ways to refine this approximation and numerically compute a displacement generator of A/sup -1/ and the solution vector x=A/sup -1/b to a linear system Ax=b by using O(log/sup 2/n) parallel arithmetic steps and n processors are presented. These results are extended to some other important classes of dense structure matrices.>

The authors compute the first N coefficients of the reciprocal r(x) of a given polynomial p(x), (r(x)p(x)=1 mod x/sup N/, p(0) not=0), by using, under the PRAM arithmetic models, O(h log N) time-steps and O((N/h)(1+2/sup -h/log/sup (h)/ N)) processors, for any h, h=1,2, . . .,log/sup */ N, provided that O(logm) steps and m processors suffice to perform DFT on m points and that log/sup (0)/ N=N, log/sup (h)/ N=log/sub 2/log/sup (h-1)/N, h=1, . . .,log/sup */N, log/sup */N=max(h:log/sup (h)/N>0). The same complexity estimates apply to some other computations, such as the division with a remainder of two polynomials of degrees O(N) and the inversion of an N*N triangular Toeplitz matrix. They also show how to extend the techniques to parallel implementation of other recursive processes, such as the evaluation modulo x/sup N/ of the m-th root, p(x)/sup 1/m/, of p(x) (for any fixed natural m), for which we need O(log N log log N) time-steps and O(N/log log N) processors. The paper demonstrates some new techniques of supereffective slowdown of parallel algebraic computations, which they combine with a technique of stream contraction.>

For pt.I see Proc. 3rd Ann. ACM Symp. Parallel Algms. Architecture, p. 180-91 (1991). The authors show that over any field, the solution set to a system of n linear equations in n unknowns can be computed in parallel with randomization simultaneously in poly-logarithmic time in n and with only as many processors as are utilized to multiply two n * n matrices. A time unit represents an arithmetic operation in the field. For singular systems the parallel timings are asymptotically as fast as those for non-singular systems, due to the avoidance of binary search in the matrix rank problem, except when the field has small positive characteristic; in that case, binary search is avoided at a somewhat higher processor count measure.>

The authors demonstrate the power of combining the techniques of algebraic computation with ones of numerical computation. They do this by improving the known methods for polynomial evaluation on a set of real points and for simulation of n charged particles on the plane. In both cases they approximate (rather than exactly compute) the solutions and do this by exploiting algebraic techniques of the algorithm design.>

recursive steps in the worst case and thus require at least the order of n time in their parallel im-We present parallel algorithms for computing all plementation, even if the number of available propair shortest paths in directed graphs.Our algocessors is not bounded.O(n) time and n2 procesrithm has time complexity O(j(n)/p + l(n) log n) sor bounds can indeed be achieved, for inst ante, on the PRAM using p processors, where I(n) is in the straightforward parallelization of the algolog non the EREW PRAM, log log n on the CRCW rithm of [Fl].(Here and hereafter we assume the PRAM, ~(n) is o(n3).On the randomized CRCW customary PRAM models of parallel computing PRAM we are able to achieve time complexity [KR].)0(n3/p + iog n) using p processors.NC algorithms are also available for this problem.However, they either need O(n3 log n) ope-

Brent's scheduling principle provides a general simulation scheme when fewer processors are available than specified by the fastest parallel algorithm.Such a scheme preserves the actual number of executed operations, and when applicable, it provides a processor balancing technique that significantly reduces the work, expressed as the number of ezecutcdde operators.In this paper we discuss a new technique, called supereffective slow-down, that yields quite fast an algorithm with work significantly smaller than that of the fastest algorithm for the same problem.This technique can be viewed as a work-preserving acceleration of an existing recursive sequential algorithm for the considered problem.The presented examples include the computation of path algebras in graphs and digraphs and various computations in linear albegra.Some of the new algorithms may have practical value; for instance, we substantially improve the performance of the known parallel algorithms for triangular linear systems of equations.

lems of computing the inverse, determinant, and rank of an n x 71 matrix.An individual step in our algorithms is an addition, subtraction, multiplication, division, or zero-test of elements in the field that the entries of the linear system generate.Gaussian elimination is a sequential method for all these computational problems over abstract fields, whose running time can be asymptotically related to the sequential complexity of n x n matrix multiplication (Bunch and Hopcroft 1974).We present processor efficient randomized parallel algorithms for solving non-singular systems and for inverting non-singular matrices.Csanky (1976) used Leverrier's approach to devise a parallel linear system solver, but the best processor count known for this approach exceeds by a factor of almost A the complexity of matrix multiplication (Preparata and Sarwate 1978), (Galil and Pan 1989).Leverrier's algorithm does not work for fields whose characteristic is positive and less than n, in which case the best known parallel algorithms needed by a factor of n more processors (Berkowitz 1984), (Chistov 1985).All previous parallel solutions compute the characteristic polynomial of the coefficient matrix without divisions.For this restricted algebraic model these algorithms are processor optimal, i.e., it appears not to be known how

Let lg stand for log2, lg(0)n = n, lg(h)n = lg lg(h-1)n, h = 1, …, lg*n, lg*n = min{h,lg(h)n ≤ 1}. Given natural N, h, 1 ≤ h ≤ lg*N, and polynomial p(x), p(O) ≠ O, we compute r(x) = p(x)-1 mod xN for the cost OA(t, P), t = h lg N, P = (N/h)lg(h)N, under the PRAM arithmetic model, that is, we need O(t) steps and O(P) processors (with t and P as above), provided DFT(m) costs OA(lg m, m). For h = lg* N, the cost bounds turn into OA(lg N lg*N, N/lg*N). The results improve [G] and apply to various related computations [BP].

We reduce several computations with Hilbert and Vandermonde type matrices to matrix computations of the Hankel-Toeplitz type (and vice versa). This unifies various known algorithms for computations with dense structured matrices and enables us to extend any progress in computations with matrices of one class to the computations with other classes of matrices. In particular, this enables us to compute the inverses and the determinants of nXn matrices of Vandermonde and Hilbert types for the cost of O(n log2n) arithmetic operations. (Previously, such results were only known for the more narrow class of Vandermonde and generalized Hilbert matrices.)

We evaluate all the real and complex zeros λ1,...,λn of an n-th degree univariate polynomial with the relative precision 1/2nc for a given positive constant c. If for all g,h, log |λg/λh-1| ≥ 1/2O(n) unless λg = λh, then we need O(n3log2n) arithmetic operations or O(n2log n) steps, n log n processors. O(n2log n) operations or O(n log n) parallel steps, n processors suffice if either all the zeros are real or for all g,h either |λg| = |λh| or 2O(n) ≥ (|λg/λh| - 1)| ≥ 1/2O(n). If all the zeros are either multiple or form complex conjugate pairs or if their moduli pairwise differ by the factors at least 1+1/nO(1), then O(n log2n) operations or O(log2n) steps, n processors suffice. Replacing 1+1/nO(1) above by 1+1/nO(loghn) for a positive h only requires to increase the time-complexity bounds by the factor loghn. Some of the presented algorithms extend Graeffe's method, other algorithms use the power sum techniques and the companion matrix computation; the latter ones are related to Bernoulli's and Leverrier's methods and to the power method and are extended in this paper to the evaluation of a matrix polynomial u(X) of degree N, (X is an n×n matrix), using O(N log N+n2.496) arithmetic operations. Such evaluation can be performed using O(log N+log2n) parallel steps, Nn+n3.496 processors or alternatively O(log2(nN)) steps, N/log N+n3.496 processors over arbitrary field of constants. Over rational constants, for almost all matrices X the number of processors can be reduced to Nn+n2.933 or to N/log N+n2.933, respectively; the bounds can be further reduced to O(log N+log2n)steps, N+n2.933 processors if u(X) is to be computed with a fixed arbitrarily high precision rather than exactly. For integer and well-conditioned matrices, the exponent 2.933 above can be decreased to 2.496. The results substantially improve the previously known upper estimates for the complexity of sequential and parallel evaluation of polynomial zeros and of matrix polynomials.

The most efficient known parallel algorithms for inversion of a nonsingular nxn matrix A or solving a linear system Ax=b over the rationals require O(log n) to the 2nd power time and M(n) square root of n processors (where M(n) is the number of processors required in order to multiply two nxn rational matrices in time O(log n)). Furthermore, all known polylog time algorithms for those problems are unstable: they require the calculations to be done with perfect precision; otherwise they give no results at all. This paper describes parallel algorithms that have good numerical stability and remain efficient as n grows large. Additional keywords: Iterations; Convergence; Newtons method; Computer architecture.

A new technique of trilinear operations of aggregating, uniting and canceling is introduced and applied to constructing fast linear noncommutative algorithms for matrix multiplication. The result is an asymptotic improvement of Strassen’s famous algorithms for matrix operations.

The acceleration of matrix multiplication MM, is based on the combination of the method of algebraic field extension due to D. Bini, M. Capovani, G. Lotti, F. Romani and S. Winograd and of trilinear aggregating, uniting and canceling due to the author. A fast algorithm of O(N2.7378) complexity for N × N matrix multiplication is derived. With A. Schönhage's Theorem about partial and total MM, our approach gives the exponent 2.6054 by the price of a serious increase of the constant.

A new technique of trilinear operations of aggregating, uniting and canceling is introduced and applied to constructing fast linear non-commutative algorithms for matrix multiplication. The result is an asymptotic improvement of Strassen's famous algorithms for matrix operations.

Fast computation of polynomials of 1 variable in the fields R and C of real and complex numbers is considered. The optimal schemes of computation with preconditioning (that is, the schemes involving the minimal number of arithmetic operations without counting preliminary treatment of coefficients) for evaluation in C are presented. The schemes which are close to optimal ones are presented for evaluation in R. The difference between the complexity of computation in R and in C is established. A new generalization of the problem is presented.