ANALYSIS OF DIFFERENT PARTITIONING SCHEMES FOR PARALLEL GRAM-SCHMIDT ALGORITHMS

S OLIVEIRA; L BORGES; M HOLZRICHTER; T SOMA

doi:10.1080/10637199808947392

Back

Journal article

ANALYSIS OF DIFFERENT PARTITIONING SCHEMES FOR PARALLEL GRAM-SCHMIDT ALGORITHMS

S OLIVEIRA, L BORGES, M HOLZRICHTER and T SOMA

Parallel algorithms and applications, Vol.14(4), pp.293-320

04/01/2000

DOI: 10.1080/10637199808947392

View Online

Abstract

In this paper we analyze implementations of parallel Gram-Schmidt orthogonalization algorithms. One of the first parallel orthogonalization of Gram-Schmidt was the row-wise partitioning of O'Leary and Whitman. In this paper we describe a pipelined implementation which uses column-wise partitioning schemes. Timing models for the column-wise parallel algorithms are derived. We compare our column-wise partitionings against the row-wise partitioning and validate our study with computational results. The pipelined orthogonalization algorithm is important because the timing analysis is independent of the architecture model. Threshold values of m max , which is the number of rows where row partitioning becomes better than column partitioning are found theoretically and verified with our experiments

Gram-Schmidt orthogonalization

Parallel algorithms

Details

Title: Subtitle: ANALYSIS OF DIFFERENT PARTITIONING SCHEMES FOR PARALLEL GRAM-SCHMIDT ALGORITHMS
Creators: S OLIVEIRA - Department of Computer Science , The University of Iowa
L BORGES - Department of Computer Science , Texas A&M University
M HOLZRICHTER - Department of Computer Science , Texas A&M University
T SOMA - Department of Computer Science , The University of Iowa
Resource Type: Journal article
Publication Details: Parallel algorithms and applications, Vol.14(4), pp.293-320
DOI: 10.1080/10637199808947392
ISSN: 1063-7192
Publisher: Taylor & Francis Group
Language: English
Date published: 04/01/2000
Academic Unit: Computer Science; Mathematics
Record Identifier: 9984002419402771

Metrics

28 Record Views