JavaScript is disabled for your browser. Some features of this site may not work without it.
Browsing by Author "Gilbert, John R."
Now showing items 113 of 13

Computing a Sparse Basis for the Null Space
Gilbert, John R.; Heath, Michael T. (Cornell University, 198601)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
Aspvall, Bengt; Gilbert, John R. (Cornell University, 198302)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 wellknown NPcomplete problem. Graph coloring is also of practical ... 
A Parallel Algorithm for Finding Fill in a Sparse Symmetric Matrix
Gilbert, John R.; Hafsteinsson, Hjalmtyr (Cornell University, 198610)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
Zmijewski, Earl; Gilbert, John R. (Cornell University, 198602)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 messagepassing multiprocessor system, such as ... 
Parallel Cholesky Factorization of Sparse Matrices
Gilbert, John R.; Hafsteinsson, Hjalmtyr (Cornell University, 198712)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 MessagePassing Multiprocessor
Gilbert, John R.; Zmijewski, Earl (Cornell University, 198701)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 messagepassing multiprocessor ... 
Predicting Fill for Sparse Orthogonal Factorization
Coleman, Thomas F.; Edenbrandt, Anders; Gilbert, John R. (Cornell University, 198310)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
Gilbert, John R. (Cornell University, 198605)We describe the results of an experiment in which the Nuprl proof development system was used in conjunction with a collection of simple proofassisting programs to constructively prove a substantial theorem of number ... 
A Separator Theorem for Chordal Graphs
Gilbert, John R.; Rose, Donald J. (Cornell University, 198210)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
Gilbert, John R.; Hutchinson, Joan P.; Tarjan, Robert Endre (Cornell University, 198207)Many divideandconquer 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
Gilbert, John R. (Cornell University, 198608)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
Gilbert, John R.; Peierls, Timothy (Cornell University, 198609)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
Zmijewski, Earl; Gilbert, John R. (Cornell University, 198504)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 ...