Parallel algorithms for banded linear systems of equations.
Item
-
Title
-
Parallel algorithms for banded linear systems of equations.
-
Identifier
-
AAI9432384
-
identifier
-
9432384
-
Creator
-
Sobze, Isdor.
-
Contributor
-
Adviser: Victor Y. Pan
-
Date
-
1994
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer Science | Mathematics
-
Abstract
-
We devise parallel algorithms for solving a nonsingular banded linear system of equations (BLS) and for computing the determinant of any banded matrix, substantially improving the previous record computational complexity estimates of W. Eberly (E). These algorithms are in NC (respectively, RNC) if the input matrix is defined over a field of characteristic zero (respectively, a finite field or a ring); they support new record bounds on the parallel time complexity of these computations and the optimum or near optimum bounds on their potential work (that is, the product of time and processor bounds); moreover, they are in {dollar}NC\sp1{dollar} or {dollar}RNC\sp1{dollar} if the bandwidth of the input matrix is a constant. We also develop several preprocessing techniques for accelerating the computation of the solution of several nonsingular BLS's, each having the same coefficient matrix A, so as to keep the potential work on solving q such BLS's asymptotically bounded by the potential work on solving a single BLS, provided that q does not exceed the bandwidth of the common input matrix A. The space requirement of our solutions is equal (up to a small multiplicative constant factor) to the space required by the best known sequential algorithms for solving the same problems.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
