16 Matching Results

Search Results

Advanced search parameters have been applied.
in creator/contributor: "Peyton, B.W."  
Results: 1 - 16
open access

Minimal Orderings Revisited

Description: When minimum orderings proved too difficult to deal with, Rose, Tarjan, and Leuker instead studied minimal orderings and how to compute them (Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5:266-283, 1976). This paper introduces an algorithm that is capable of computing much better minimal orderings much more efficiently than the algorithm in Rose et al. The new insight is a way to use certain structures and concepts from modern sparse Cholesky solvers to re-express one o… more
Date: July 1, 1999
Creator: Peyton, B. W.
Item Type: Refine your search to only Report
Partner: UNT Libraries Government Documents Department
open access

A tight and explicit representation of Q in sparse QR factorization

Description: In QR factorization of a sparse m{times}n matrix A (m {ge} n) the orthogonal factor Q is often stored implicitly as a lower trapezoidal matrix H known as the Householder matrix. This paper presents a simple characterization of the row structure of Q, which could be used as the basis for a sparse data structure that can store Q explicitly. The new characterization is a simple extension of a well known row-oriented characterization of the structure of H. Hare, Johnson, Olesky, and van den Driessc… more
Date: May 1, 1992
Creator: Ng, E. G. & Peyton, B. W.
Item Type: Refine your search to only Report
Partner: UNT Libraries Government Documents Department
open access

Block sparse Cholesky algorithms on advanced uniprocessor computers

Description: As with many other linear algebra algorithms, devising a portable implementation of sparse Cholesky factorization that performs well on the broad range of computer architectures currently available is a formidable challenge. Even after limiting our attention to machines with only one processor, as we have done in this report, there are still several interesting issues to consider. For dense matrices, it is well known that block factorization algorithms are the best means of achieving this goal.… more
Date: December 1, 1991
Creator: Ng, E. G. & Peyton, B. W.
Item Type: Refine your search to only Report
Partner: UNT Libraries Government Documents Department
open access

A tight and explicit representation of Q in sparse QR factorization

Description: In QR factorization of a sparse m{times}n matrix A (m {ge} n) the orthogonal factor Q is often stored implicitly as a lower trapezoidal matrix H known as the Householder matrix. This paper presents a simple characterization of the row structure of Q, which could be used as the basis for a sparse data structure that can store Q explicitly. The new characterization is a simple extension of a well known row-oriented characterization of the structure of H. Hare, Johnson, Olesky, and van den Driessc… more
Date: May 1, 1992
Creator: Ng, E. G. & Peyton, B. W.
Item Type: Refine your search to only Report
Partner: UNT Libraries Government Documents Department
open access

Block sparse Cholesky algorithms on advanced uniprocessor computers

Description: As with many other linear algebra algorithms, devising a portable implementation of sparse Cholesky factorization that performs well on the broad range of computer architectures currently available is a formidable challenge. Even after limiting our attention to machines with only one processor, as we have done in this report, there are still several interesting issues to consider. For dense matrices, it is well known that block factorization algorithms are the best means of achieving this goal.… more
Date: December 1, 1991
Creator: Ng, E. G. & Peyton, B. W.
Item Type: Refine your search to only Report
Partner: UNT Libraries Government Documents Department
open access

An introduction to chordal graphs and clique trees

Description: Clique trees and chordal graphs have carved out a niche for themselves in recent work on sparse matrix algorithms, due primarily to research questions associated with advanced computer architectures. This paper is a unified and elementary introduction to the standard characterizations of chordal graphs and clique trees. The pace is leisurely, as detailed proofs of all results are included. We also briefly discuss applications of chordal graphs and clique trees in sparse matrix computations.
Date: November 1, 1992
Creator: Blair, J. R. S. & Peyton, B. W.
Item Type: Refine your search to only Report
Partner: UNT Libraries Government Documents Department
open access

An efficient algorithm to compute row and column counts for sparse Cholesky factorization

Description: Let an undirected graph G be given, along with a specified depth- first spanning tree T. We give almost-linear-time algorithms to solve the following two problems: First, for every vertex v, compute the number of descendants w of v for which some descendant of w is adjacent (in G) to v. Second, for every vertx v, compute the number of ancestors of v that are adjacent (in G) to at least one descendant of v. These problems arise in Cholesky and QR factorizations of sparse matrices. Our algorithms… more
Date: September 1, 1992
Creator: Gilbert, J. R.; Ng, E. G. & Peyton, B. W.
Item Type: Refine your search to only Report
Partner: UNT Libraries Government Documents Department
open access

An efficient algorithm to compute row and column counts for sparse Cholesky factorization

Description: Let an undirected graph G be given, along with a specified depth- first spanning tree T. We give almost-linear-time algorithms to solve the following two problems: First, for every vertex v, compute the number of descendants w of v for which some descendant of w is adjacent (in G) to v. Second, for every vertx v, compute the number of ancestors of v that are adjacent (in G) to at least one descendant of v. These problems arise in Cholesky and QR factorizations of sparse matrices. Our algorithms… more
Date: September 1, 1992
Creator: Gilbert, J. R.; Ng, E. G. & Peyton, B. W.
Item Type: Refine your search to only Report
Partner: UNT Libraries Government Documents Department
open access

Computing connection coefficients of compactly supported wavelets on bounded intervals

Description: Daubechies wavelet basis functions have many properties that make them desirable as a basis for a Galerkin approach to solving PDEs: they are orthogonal, with compact support, and their connection coefficients can be computed. The method developed by Latto et al. to compute connection coefficients does not provide the correct inner product near the endpoints of a bounded interval, making the implementation of boundary conditions problematic. Moreover, the highly oscillatory nature of the wavele… more
Date: April 1, 1997
Creator: Romine, C. H. & Peyton, B. W.
Item Type: Refine your search to only Report
Partner: UNT Libraries Government Documents Department
open access

PICL

Description: PICL is a subroutine library that can be used to develop parallel programs that are portable across several distributed memory multiprocessors. The library provides portable syntax for the key communication primitives and related system calls required to program these machines It also provides portable routines to perform certain widely-used, high-level communication operations, such as global broadcast and global sum. Finally, the library provides an execution tracing facility that can be used… more
Date: July 1, 1990
Creator: Geist, G. A.; Heath, M. T.; Peyton, B. W. & Worley, P. H.
Item Type: Refine your search to only Report
Partner: UNT Libraries Government Documents Department
open access

A user's guide to PICL a portable instrumented communication library

Description: This report is the PCL user's guide. It contains an overview of PICL and how it is used. Examples in C Fortran are included. PICL is a subroutine library that can be used to develop parallel programs that are portable across several distributed-memory multiprocessors. PICL provides a portable syntax for key communication primitives and related system calls. It also provides portable routines to perform certain widely-used, high-level communication operations, such as global broadcast and global… more
Date: October 1, 1990
Creator: Geist, G. A.; Heath, M. T.; Peyton, B. W. & Worley, P. H.
Item Type: Refine your search to only Report
Partner: UNT Libraries Government Documents Department
open access

Partitioning a chordal graph into transitive subgraphs for parallel sparse triangular solution

Description: A recent approach for solving sparse triangular systems of equations on massively parallel computers employs a factorization of the triangular coefficient matrix to obtain a representation of its inverse in product form. The number of general communication steps required by this approach is proportional to the number of factors in the factorization. The triangular matrix can be symmetrically permuted to minimize the number of factors over suitable classes of permutations, and thereby the comple… more
Date: December 1, 1992
Creator: Peyton, B. W.; Pothen, A. & Yuan, Xiaoqing
Item Type: Refine your search to only Report
Partner: UNT Libraries Government Documents Department
open access

On finding minimum-diameter clique trees

Description: It is well-known that any chordal graph can be represented as a clique tree (acyclic hypergraph, join tree). Since some chordal graphs have many distinct clique tree representations, it is interesting to consider which one is most desirable under various circumstances. A clique tree of minimum diameter (or height) is sometimes a natural candidate when choosing clique trees to be processed in a parallel computing environment. This paper introduces a linear time algorithm for computing a minimum-… more
Date: August 1, 1991
Creator: Blair, J.R.S. (Tennessee Univ., Knoxville, TN (United States). Dept. of Computer Science) & Peyton, B.W. (Oak Ridge National Lab., TN (United States))
Item Type: Refine your search to only Report
Partner: UNT Libraries Government Documents Department
open access

An introduction to chordal graphs and clique trees

Description: Clique trees and chordal graphs have carved out a niche for themselves in recent work on sparse matrix algorithms, due primarily to research questions associated with advanced computer architectures. This paper is a unified and elementary introduction to the standard characterizations of chordal graphs and clique trees. The pace is leisurely, as detailed proofs of all results are included. We also briefly discuss applications of chordal graphs and clique trees in sparse matrix computations.
Date: November 1, 1992
Creator: Blair, J.R.S. (Tennessee Univ., Knoxville, TN (United States). Dept. of Computer Science) & Peyton, B.W. (Oak Ridge National Lab., TN (United States))
Item Type: Refine your search to only Report
Partner: UNT Libraries Government Documents Department
open access

A compute-ahead implementation of the fan-in sparse distributed factorization scheme

Description: In this report, we consider a compute-ahead computational technique in the distributed factorization of large sparse matrices using the fan-in parallel scheme. Experimental results on an Intel iPSC/2 hypercube are provided to demonstrate the relevance and effectiveness of this technique. Fortran source code is also included in an appendix. 9 refs., 2 figs., 1 tab.
Date: August 1, 1990
Creator: Ashcraft, C.; Eisenstat, S.C.; Sherman, A.H. (Yale Univ., New Haven, CT (USA). Dept. of Computer Science); Liu, J.W.H. (York Univ., Toronto, ON (Canada). Dept. of Computer Science) & Peyton, B.W. (Oak Ridge National Lab., TN (USA))
Item Type: Refine your search to only Article
Partner: UNT Libraries Government Documents Department
open access

Partitioning a chordal graph into transitive subgraphs for parallel sparse triangular solution

Description: A recent approach for solving sparse triangular systems of equations on massively parallel computers employs a factorization of the triangular coefficient matrix to obtain a representation of its inverse in product form. The number of general communication steps required by this approach is proportional to the number of factors in the factorization. The triangular matrix can be symmetrically permuted to minimize the number of factors over suitable classes of permutations, and thereby the comple… more
Date: December 1, 1992
Creator: Peyton, B.W. (Oak Ridge National Lab., TN (United States)); Pothen, A. (Waterloo Univ., ON (Canada). Dept. of Computer Science) & Yuan, Xiaoqing (IBM Canada Lab., North York, Ontario (Canada))
Item Type: Refine your search to only Report
Partner: UNT Libraries Government Documents Department
Back to Top of Screen