In this paper, a BSP (bulk synchronous parallel) bareiss algorithm for Toeplitz system is described. We investigate various data distribution and scheduling strategies for mapping a typical class of systolic array alg...
详细信息
In this paper, a BSP (bulk synchronous parallel) bareiss algorithm for Toeplitz system is described. We investigate various data distribution and scheduling strategies for mapping a typical class of systolic array algorithms onto BSP machines. Load balance, both in communication and computation, as well as linear speedup have been achieved for the Toeplitz system solver and at the same time the minimum memory requirement is achieved. An implementation has been tested on Sun workstations, an SGI Power Challenge, and an IBM SP?, using the Oxford BSPlib (Hill et al., 1997. (C) 1999 Academic Press.
This paper contains a numerical stability analysis of factorization algorithms for computing the Cholesky decomposition of symmetric positive definite matrices of displacement rank 2. The algorithms in the class can b...
详细信息
This paper contains a numerical stability analysis of factorization algorithms for computing the Cholesky decomposition of symmetric positive definite matrices of displacement rank 2. The algorithms in the class can be expressed as sequences of elementary downdating steps. The stability of the factorization algorithms follows directly from the numerical properties of algorithms for realizing elementary downdating operations. It is shown that the bareiss algorithm for factorizing a symmetric positive definite Toeplitz matrix is in the class and hence the bareiss algorithm is stable. Some numerical experiments that compare behavior of the bareiss algorithm and the Levinson algorithm are presented. These experiments indicate that generally (when the reflection coefficients are not all of the same sign) the Levinson algorithm can give much larger residuals than the bareiss algorithm.
In this paper we analyze the computational costs of various operations and algorithms in algebraic number fields using exact arithmetic. Let K be an algebraic number field. In the first half of the paper, we calculate...
详细信息
In this paper we analyze the computational costs of various operations and algorithms in algebraic number fields using exact arithmetic. Let K be an algebraic number field. In the first half of the paper, we calculate the running time and the size of the output of many operations in K in terms of the size of the input and the parameters of K. We include some earlier results about these, but we go further than them, e.g. we also analyze some R-specific operations in K like less-than comparison. In the second half of the paper, we analyze two algorithms: the bareiss algorithm, which is an integer-preserving version of the Gaussian elimination, and the LLL algorithm, which is for lattice basis reduction. In both cases, we extend the algorithm from Zn to Kn, and give a polynomial upper bound on the running time when the computations in K are performed exactly (as opposed to floating-point approximations). (c) 2023 Elsevier Ltd. All rights reserved.
暂无评论