THE INSTABILITY OF PARALLEL PREFIX MATRIX MULTIPLICATION

作     者：MATHIAS, R 

出 版 物：《SIAM JOURNAL ON SCIENTIFIC COMPUTING》 (工业与应用数学会科学计算杂志)

年 卷 期：1995年第16卷第4期

页      面：956-973页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：PARALLEL PREFIX PARALLEL COMPUTATION SYMMETRICAL EIGENPROBLEM ERROR ANALYSIS TRIANGULAR FACTORIZATION 

摘      要：It is shown that when parallel prefix is used to compute the leading principal miners of a tridiagonal matrix T within a bisection algorithm to compute the eigenvalues of T the relative error in the computed ei,aenvalues can be as great as epsilon kappa(3), where epsilon is machine precision and kappa is the condition number for the problem of computing the eigenvalues of T. An ideal algorithm, like serial bisection, would have forward error epsilon kappa. Forward and backward error bounds for the computed leading principal miners are given. Also, error bounds for the parallel prefix computation of the partial products of a sequence of matrices are given and some applications to other related problems in numerical Linear algebra, including the parallel implementation of the differential qd algorithm, are presented.