Change search
ReferencesLink to record
Permanent link

Direct link
Solving Narrow Banded Systems on Ensemble Architectures
KTH, School of Computer Science and Communication (CSC), Centres, Centre for High Performance Computing, PDC. (Parallelldatorcentrum)
1985 (English)In: ACM Transactions on Mathematical Software, ISSN 0098-3500, Vol. 11, no 3, 271-288 p.Article in journal (Refereed) Published
Abstract [en]

We present concurrent algorithms for the solution of narrow banded systems on ensemble architectures, and analyze the communication and arithmetic complexities of the algorithms. The algorithms consist of three phases. In phase 1, a block tridiagonal system of reduced size is produced through largely local operations. Diagonal dominance is preserved. If the original system is positive, definite, and symmetric, so is the reduced system. It is solved in a second phase, and the remaining variables obtained through local back substitution in a third phase. With a sufficient number of processing elements, there is no first and third phase. We investigate the arithmetic and communicationcomplexity of Gaussian elimination and block cyclic reduction for the solution of the reduced system on boolean cubes, perfect shuffle and shuffle-exchange networks, binary trees, and linear arrays. With an optimum number of processors, the minimum solution time on a linear array is of an order that ranges from Om2Nm to O(m3 + m3log2(N/m)) depending on the bandwidth, the dimension of the problem, and the times for communication and arithmetic. For boolean cubes, cube-connected cycles, prefect shuffle and shuffle-exchange networks, and binary trees, the minimum time is Om3+m3log 2N/m including the communication complexity

Place, publisher, year, edition, pages
1985. Vol. 11, no 3, 271-288 p.
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-91119DOI: 10.1145/214408.214418OAI: diva2:508325
NR 20140805Available from: 2012-03-08 Created: 2012-03-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Johnsson, Lennart
By organisation
Centre for High Performance Computing, PDC
In the same journal
ACM Transactions on Mathematical Software
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 16 hits
ReferencesLink to record
Permanent link

Direct link