Now showing items 1-13 of 13

• #### Computing a Sparse Basis for the Null Space ﻿

(Cornell University, 1986-01)
We present algorithms for computing a sparse basis for the null space of a sparse underdetermined matrix. We describe several possible computational strategies, both combinatorial and noncombinatorial in nature, and we ...
• #### Graph Coloring Using Eigenvalue Decomposition ﻿

(Cornell University, 1983-02)
Determining whether the vertices of a graph can be colored using $k$ different colors so that no two adjacent vertices receive the same color is a well-known NP-complete problem. Graph coloring is also of practical ...
• #### A Parallel Algorithm for Finding Fill in a Sparse Symmetric Matrix ﻿

(Cornell University, 1986-10)
We describe a parallel algorithm for finding the fill that occurs when a sparse symmetric positive definite matrix A is factored into its Cholesky factor L. The algorithm is in two steps: First we determine the elimination ...
• #### A Parallel Algorithm for Large Sparse Cholesky Factorization on a Multiprocessor ﻿

(Cornell University, 1986-02)
We develop an algorithm for computing the symbolic and numeric Cholesky factorization of a large sparse symmetric positive definite matrix. The algorithm is intended for a message-passing multiprocessor system, such as ...
• #### Parallel Cholesky Factorization of Sparse Matrices ﻿

(Cornell University, 1987-12)
We describe a parallel algorithm for finding the Cholesky factorization of a sparse symmetric positive definite matrix A. The algorithm runs in $O(h \log n)$ time with $m\*$ processors, where $h$ is the height of A's ...
• #### A Parallel Graph Partitioning Algorithm for a Message-Passing Multiprocessor ﻿

(Cornell University, 1987-01)
We develop a parallel algorithm for partitioning the vertices of a graph into $p \geq 2$ sets in such a way that few edges connect vertices in different sets. The algorithm is intended for a message-passing multiprocessor ...
• #### Predicting Fill for Sparse Orthogonal Factorization ﻿

(Cornell University, 1983-10)
In solving large sparse linear least squares problems $Ax \cong b$, several different numeric methods involve computing the same upper triangular factor $R$ of $A$. It is of interest to be able to compute the nonzero ...
• #### Predicting Structure in Sparse Matrix Computations ﻿

(Cornell University, 1986-05)
We describe the results of an experiment in which the Nuprl proof development system was used in conjunction with a collection of simple proof-assisting programs to constructively prove a substantial theorem of number ...
• #### A Separator Theorem for Chordal Graphs ﻿

(Cornell University, 1982-10)
Chordal graphs are undirected graphs in which every cycle of length at least four has a chord. They are sometimes called rigid circuit graphs or perfect elimination graphs; the last name reflects their utility in modelling ...
• #### A Separator Theorem for Graphs of Bounded Genus ﻿

(Cornell University, 1982-07)
Many divide-and-conquer algorithms on graphs are based on finding a small set of vertices or edges whose removal divides the graph roughly in half. Most graphs do not have the necessary small separators, but some useful ...
• #### Some Nested Dissection Order is Nearly Optimal ﻿

(Cornell University, 1986-08)
The minimum fill problem is to reorder the rows and columns of a given sparse symmetric matrix so that its triangular factor is as sparse as possible. Equivalently, it is to find the smallest set of edges whose addition ...
• #### Sparse Partial Pivoting in Time Proportional to Arithmetic Operations ﻿

(Cornell University, 1986-09)
Existing sparse partial pivoting algorithms can spend asymptomatically more time manipulating data structures than doing arithmetic, although they are tuned to be efficient on many large problems. We present an algorithm ...
• #### Wide Quotient Trees for Finite Element Problems ﻿

(Cornell University, 1985-04)
In solving the system of linear equations $Ax = b$ where $A$ is an $n \times n$ large sparse symmetric positive definite matrix, one important objective is to minimize fill. One approach is to partition the matrix so ...