Multilevel Linear Dimensionality Reduction for Data Analysis using Nearest-Neighbor Graphs ∗ (2009)
Sophia Sakellaridi, Yousef Saad
Dimension reduction techniques can be time-consuming when the data set is large. This paper presents a multilevel framework to reduce the size of the data set, prior to performing dimension...
Large Sparse Matrix Problems in Scientific and Industrial Applications (2009)
Esmond G. Ng, Yousef Saad, Wei-pai Tang
Sponsored by In collaboration with Soci'et'e de Math'ematique Appliqu'ees et Industrielles / Groupe pourl'Avancement des M'ethodes Num'eriques de...
We are interested in computing the Fermi-Dirac matrix function in which the matrix argument is the Hamiltonian matrix arising from Density Function Theory (DFT) applications. More precisely, we are...
MIQR: A MULTILEVEL INCOMPLETE QR PRECONDITIONER FOR LARGE SPARSE LEAST-SQUARES PROBLEMS ∗ (2008)
Abstract. This paper describes a Multilevel Incomplete QR (MIQR) factorization for solving large sparse least-squares problems. The algorithm builds the factorization by exploiting structural...
1 Schur complement preconditioners for distributed general sparse linear systems ⋆ (2008)
Summary. This paper discusses the Schur complement viewpoint when developing parallel preconditioners for general sparse linear systems. Schur complement methods are pervasive in numerical linear...
A Chebyshev-Davidson algorithm for large symmetric eigenvalue problems (2008)
Abstract. A polynomial filtered Davidson-type algorithm is proposed for symmetric eigenproblems, in which the correction-equation of the Davidson approach is replaced by a polynomial filtering step....
A Chebyshev-Davidson algorithm for large symmetric eigenvalue problems (2008)
A polynomial filtered Davidson-type algorithm is proposed for solving symmetric eigenproblems. The correction-equation of the Davidson approach is replaced by a polynomial filtering step. The new...
Abstract Nonlinear Krylov acceleration for CFD-based (2008)
Zhengkun Feng, Azzeddine Soulaïmani, Yousef Saad
A nonlinear computational aeroelasticity model based on the Euler equations of compressible flows and the linear elastodynamic equations for structures is developed. The Euler equations are solved on...
Divide and Conquer Strategies for Effective Information Retrieval ∗ (2008)
The standard application of Latent Semantic Indexing (LSI), a well-known technique for information retrieval, requires the computation of a partial Singular Value Decomposition (SVD) of the...
Self-Consistent-Field calculations using Chebyshev-filtered subspace iteration (2008)
Yunkai Zhou, Yousef Saad, Murilo L. Tiago, James R
Abstract. The power of density functional theory is often limited by the high computational demand in solving an eigenvalue problem at each self-consistent-field (SCF) iteration. The method presented...
Multilevel Linear Dimensionality Reduction using Hypergraphs for Data Analysis ∗ Haw-ren Fang (2008)
Classical algorithms used for dimension reduction can be time-consuming when the data set is large. In this paper we consider a method based on hypergraph coarsening to find a smaller set of data...
Self-Consistent-Field calculations using Chebyshev-filtered subspace iteration (2008)
Yunkai Zhou, Yousef Saad, Murilo L. Tiago, James R
Abstract. The power of Density Functional Theory is often limited by the high computational demand in solving an eigenvalue problem at each Self-Consistent-Field (SCF) iteration. The method presented...
A PARALLEL MULTILEVEL ILU FACTORIZATION BASED ON A HIERARCHICAL GRAPH DECOMPOSITION ∗ (2008)
Abstract. PHIDAL (Parallel Hierarchical Interface Decomposition ALgorithm) is a parallel incomplete factorization method which exploits a hierarchical interface decomposition of the adjacency graph...
.
Turbo charging time-dependent density-functional theory with Lanczos chains (2008)
Rocca, Dario, Gebauer, Ralph, Saad, Yousef, Baroni, Stefano
We introduce a new implementation of time-dependent density-functional theory which allows the \emph{entire} spectrum of a molecule or extended system to be computed with a numerical effort...
Electronic Structure Calculations In Plane-Wave Codes Without Diagonalization (2008)
Laurent O. Jay, Hanchul Kim, Yousef Saad, James R. Chelikowsky
. We present an algorithm to reduce the computational complexity for plane-wave codes used in electronic structure calculations. Our proposed algorithm avoids the diagonalization of large Hermitian...
Turbo charging time-dependent density-functional theory with Lanczos chains (2008)
Rocca, Dario, Gebauer, Ralph, Saad, Yousef, Baroni, Stefano
We introduce a new implementation of time-dependent density-functional theory which allows the \emph{entire} spectrum of a molecule or extended system to be computed with a numerical effort...
Farthest Centroids Divisive Clustering ∗ (2008)
A method is presented to partition a given set of data entries embedded in Euclidean space by recursively bisecting clusters into smaller ones. The initial set is subdivided into two subsets whose...
Jie Chen, Haw-ren Fang, Yousef Saad
Nearest neighbor graphs are widely used in data mining and machine learning. The brute-force method to compute the exact kNN graph takes Θ(dn 2) time for n data points in the d dimensional Euclidean...
This paper introduces several strategies to deal with pivot blocks in multi-level block incomplete LU factorization (BILUM) preconditioning techniques. These techniques are aimed at increasing the...
Matthias Bollhofer, Yousef Saad
This paper discusses the relations between a broad class of incomplete LU factorization techniques and factorized sparse approximate inverse techniques based on computing triangular matrices Z # W...
Electronic Structure Calculations For Plane-Wave Codes Without Diagonalization (2007)
Laurent O. Jay, Hanchul Kim, Yousef Saad, James R. Chelikowsky
. We present an algorithm to reduce the computational complexity for plane-wave codes used in electronic structure calculations. The proposed algorithm avoids the diagonalization of large Hermitian...
Azzeddine Soulaimani, Notre-dame Ouest, Yousef Saad, Abdessamad Qaddouri
This paper discusses finite element solution methods for simulating unsteady three-dimensional free surface flows. Parallelization of the code is carried out using PSPARSLIB and the MPI message...
Electronic Structure Calculations in Plane-Wave Codes without Diagonalization (2007)
Laurent O. Jay, Hanchul Kim, Yousef Saad, James R. Chelikowsky
. We present an algorithm to reduce the computational complexity for plane-wave codes used in electronic structure calculations. Our proposed algorithm avoids the diagonalization of large Hermitian...
Modified Krylov acceleration for parallel environments (2007)
Caroline Le Calvez, Yousef Saad
This paper considers a few variants of Krylov subspace techniques for solving linear systems on parallel computers. The goal of these variants is to avoid global dotproducts which hamper parallelism...
Eigenvalue bounds from the Schur form (2007)
Thierry Braconnier, Yousef Saad
Computing the partial Schur form of a matrix is a common kernel in widely used software for solving eigenvalues problems. Partial Schur forms and Schur vectors also arise naturally in deflation...
Sergey Kuznetsov, Gen-ching Lo, Yousef Saad
Abstract. This paper discusses a few algorithms and their implementations for solving distributed general sparse linear systems. The preconditioners used are all variations of techniques originating...
parallel solution strategies for distributed sparse linear systems
In this paper, a block LU preconditioner for saddle point problems is presented. The main difference between the approach presented here and that of other studies is that an explicit, accurate...
C. Le Calvez, Y. Saad, Sciences Et, Technologies De Lille, Caroline Le Calvez, ...
Modified Krylov acceleration for parallel environments
Y.Saad, “Predicting the Properties of Semiconductor Clusters,” Theory of Atomic and Molecular (2007)
James R. Chelikowsky, Serdar Ogut, Igor Vasiliev, Andreas Stathopoulos, Yousef Saad
Abstract. The electronic and structural properties of semiconductor clusters are examined using pseudopotentials and a real space method. Examples of this method are applied to predict the...
Crout versions of ILU for general sparse matrices (2007)
Na Li Yousef, Na Li, Yousef Saad, Edmond Chow
This paper presents an e#cient implementation of incomplete LU (ILU) factorizations that are derived from the Crout version of Gaussian elimination (GE). At step k of the elimination, the k-th row of...
Electronic Structure Calculations in Plane-Wave Codes without Diagonalization (2007)
Laurent O. Jay, Hanchul Kim, Yousef Saad, James R. Chelikowsky
We present an algorithm to reduce the computational complexity for plane-wave codes used in electronic structure calculations. Our proposed algorithm avoids the diagonalization of large Hermitian...
Parallel Self-Consistent-Field Calculations via Chebyshev-Filtered Subspace Acceleration (2007)
Zhou, Yunkai, Saad, Yousef, Tiago, Murilo L., Chelikowsky, James R.
Solving the Kohn-Sham eigenvalue problem constitutes the most computationally expensive part in self-consistent density functional theory (DFT) calculations. In a previous paper, we have proposed a...
Kokiopoulou, Effrosyni, Saad, Yousef
This paper considers the problem of dimensionality reduction by orthogonal projection techniques. The main feature of the proposed techniques is that they attempt to preserve both the intrinsic...
Luc Giraud, Esmond G. Ng, Yousef Saad, Wei-pai Tang
The 2007 International Conference on Preconditioning Techniques for Large Sparse Matrix Problems in Scientific and Industrial Applications, Preconditioning 2007, is the fifth in a series of...
Efficient Algorithms Physical Model Approximations Numerical Simulation (2007)
structure calculations
Daniel Osei-kuffuor, Lingzhu Kong, Yousef Saad, James R. Chelikowsky
This paper analyzes the performance of a few preconditioners for solving the complex linear systems which originate from the application of real space pseudopotential methods in the study of electron...
Two Classes of Multisecant Methods for Nonlinear Acceleration ∗ (2007)
Many applications in science and engineering lead to models which require solving large-scale fixed point problems, or equivalently, systems of nonlinear equations. Several successful techniques for...
Hypergraph Partitioning for Parallel Iterative Solution of General Sparse Linear Systems ∗ (2007)
Masha Sosonkina, Bora Uçar, Yousef Saad
The efficiency of parallel iterative methods for solving linear systems, arising from reallife applications, depends greatly on matrix characteristics and on the amount of parallel overhead. It is...
The Evolution of Magnetism in Iron from the Atom to the Bulk (2006)
Tiago, Murilo L., Zhou, Yunkai, Alemany, M. M. G., Saad, Yousef, Chelikowsky, James R.
The evolution of the magnetic moment in iron clusters containing 20 to 400 atoms is investigated using first-principles numerical calculations based on density-functional theory and real-space...
A greedy strategy for coarse-grid selection (2006)
Efficient solution of the very large linear systems that arise in numerical modelling of real-world applications is often only possible through the use of multilevel techniques. While highly...
Multilevel preconditioners constructed from inverse-based ILUs (2006)
Matthias Bollhöfer, Yousef Saad
This paper analyzes dropping strategies in a multilevel incomplete LU decomposition context and presents a few of strategies for obtaining related ILUs with enhanced robustness. The analysis shows...
Parallel self-consistent-field calculations using chebyshev-filtered subspace acceleration (2006)
Yunkai Zhou, Yousef Saad, Murilo L. Tiago, James R. Chelikowsky
Solving the Kohn-Sham eigenvalue problem constitutes the most computationally expensive part in self-consistent density functional theory (DFT) calculations. A nonlinear Chebyshev-filtered subspace...
A greedy strategy for coarse-grid selection (2006)
Efficient solution of the very large linear systems that arise in numerical modelling of real-world applications is often only possible through the use of multilevel techniques. While highly...
Numerical methods for electronic structure calculations of materials (2006)
Yousef Saad, James R. Chelikowsky, Suzanne M. Shontz
The goal of this article is to give an overview of numerical problems encountered when determining the electronic structure of materials and the rich variety of techniques used to solve these...
On correction equations and domain decomposition for computing smallest eigenvalues (2006)
invariant subspaces
Greedy coarsening strategies for non-symmetric problems (2006)
The solution of large-scale linear systems in computational science and engineering requires efficient solvers and preconditioners. Often the most effective such techniques are those based on...
On correction equations and domain decomposition for computing invariant subspaces (2005)
Philippe, Bernard, Saad, Yousef
This paper considers a number of schemes for computing an approximate invariant subspace associated with the smallest eigenvalues of a sparse symmetric (real) matrix. The approach taken is that of...
On correction equations and domain decomposition for computing invariant subspaces (2005)
Philippe, Bernard, Saad, Yousef
This paper considers a number of schemes for computing an approximate invariant subspace associated with the smallest eigenvalues of a sparse symmetric (real) matrix. The approach taken is that of...
On correction equations and domain decomposition for computing invariant subspaces (2005)
Philippe, Bernard, Saad, Yousef
This paper considers a number of schemes for computing an approximate invariant subspace associated with the smallest eigenvalues of a sparse symmetric (real) matrix. The approach taken is that of...
On correction equations and domain decomposition for computing invariant subspaces (2005)
Philippe, Bernard, Saad, Yousef
This paper considers a number of schemes for computing an approximate invariant subspace associated with the smallest eigenvalues of a sparse symmetric (real) matrix. The approach taken is that of...
Multilevel ILU with reorderings for diagonal dominance (2005)
This paper presents a preconditioning method based on combining two-sided permutations with a multilevel approach. The nonsymmetric permutation exploits a greedy strategy to put large entries of the...
Yousef Saad, Discretization Of Pdes, Preconditioning Techniques
• Sparse matrices and sparsity • Basic iterative methods (Relax-ation..) Part 2 • Projection methods • Krylov subspace methods
Polynomial filtered lanczos iterations with applications in density functional theory (2005)
C. Bekas, E. Kokiopoulou, Yousef Saad
The most expensive part of all Electronic Structure Calculations based on Density Functional Theory, lies in the computation of an invariant subspace associated with some of the smallest eigenvalues...
Filtered conjugate residual-type algorithms with applications (2005)
In a number of applications, certain computations to be done with a given matrix are performed by replacing this matrix by its best low rank approximation. This has the effect of yielding the most...
Split preconditioning. Assume M is factored: M = MLMR. (2005)
Yousef Saad, Preconditioning Techniques
Basic idea is to use the Krylov subspace method on a modified system such as M −1 Ax = M −1 b. • The matrix M −1 A need not be formed explicitly; only need to solve Mw = v whenever needed....
Computing charge densities with partially reorthogonalized lanczos (2005)
Constantine Bekas, Yousef Saad, Murilo L. Tiago, James R. Chelikowsky
This paper considers the problem of computing charge densities in a density functional theory (DFT) framework. In contrast to traditional, diagonalization-based, methods, we utilize a technique which...
• Eigenvalue problems • Applications – (2005)
Yousef Saad, Krylov Subspace Methods, Preconditioning Techniques, Preconditioning Basic Principles
ation..)
Computation of Smallest Eigenvalues Using Spectral Schur Complements (2005)
Constantine Bekas, Yousef Saad
The Automated Multilevel Substructing method (AMLS ) was recently presented as an alternative to well-established methods for computing eigenvalues of large matrices in the context of structural...
Polynomial filtered lanczos iterations with applications in density functional theory (2005)
C. Bekas, E. Kokiopoulou, Yousef Saad
The most expensive part of all Electronic Structure Calculations based on Density Functional Theory, lies in the computation of an invariant subspace associated with some of the smallest eigenvalues...
Computing charge densities with partially reorthogonalized lanczos (2005)
Constantine Bekas, Yousef Saad, Murilo L. Tiago, James R. Chelikowsky
This paper considers the problem of computing charge densities in a density functional theory (DFT) framework. In contrast to traditional, diagonalization-based, methods, we utilize a technique which...
Orthogonal Neighborhood Preserving Projections (2005)
Effrosyni Kokiopoulou, Student Member, Yousef Saad
projection-based dimensionality reduction technique
Block Krylov-Schur method for large symmetric eigenvalue problems, tech (2004)
Abstract. Stewart’s recent Krylov-Schur algorithm offers two advantages over Sorensen’s implicitly restarted Arnoldi (IRA) algorithm. The first is ease of deflation of converged Ritz vectors, the...
James R. Chelikowsky, Yousef Saad
§.2 Quantum descriptions of matter................. 8 §.2.1 The Hartree approximation............... 11
SchurRAS: A restricted version of the overlapping Schur complement preconditioner (2004)
This paper presents a preconditioner based on solving approximate Schur complement systems with overlapping restricted additive Schwarz methods (RAS). The construction of the preconditoner, called...
Computation of smallest eigenvalues using spectral schur complements (2004)
Constantine Bekas, Yousef Saad
Abstract. The Automated Multilevel Substructuring method (AMLS) was recently presented as an alternative to well-established methods for computing eigenvalues of large matrices in the context of...
Polynomial filtering in latent semantic indexing for information retrieval (2004)
Latent Semantic Indexing (LSI) is a well established and effective framework for conceptual information retrieval. In traditional implementations of LSI the semantic structure of the collection is...
Crout versions of ILU factorization with pivoting for sparse symmetric matrices (2004)
Abstract. The Crout variant of ILU preconditioner (ILUC) developed recently has been shown to have a number of advantages over ILUT, the conventional row-based ILU preconditioner [14]. This paper...
Crout versions of ILU for general sparse matrices (2002)
Na Li, Yousef Saad, Edmond Chow
This paper presents an e#cient implementation of incomplete LU #ILU# factorizations that are derived from the Crout version of Gaussian elimination #GE#. At step k of the elimination, the k-th rowofU...
Adapting Algebraic Recursive Multilevel Solvers (ARMS) for Solving CFD Problems (2002)
Yousef Saad, Azzeddine Soulaimani, Ridha Touihri
This paper presents results using preconditioners that are based on a number of variations of the Algebraic Recursive Multilevel Solver (ARMS). ARMS is a recursive block ILU factorization based on a...
Crout versions of ILU for general sparse matrices (2002)
Na Li, Yousef Saad, Edmond Chow
This paper presents an efficient implementation of incomplete LU (ILU) factorizations that are derived from the Crout version of Gaussian elimination (GE). At step k of the elimination, the k-th row...
Least-Squares Polynomial Filters for Ill-Conditioned Linear Systems (2001)
Erhel, Jocelyne, Guyomarc'H, Frédéric, Saad, Yousef
An important problem which arises in several applications is to find the solution of an ill-conditioned Symmetric Semi-Positive Definite linear system whose right-hand side is perturbed by noise. In...
Least-Squares Polynomial Filters for Ill-Conditioned Linear Systems (2001)
Erhel, Jocelyne, Guyomarc'H, Frédéric, Saad, Yousef
An important problem which arises in several applications is to find the solution of an ill-conditioned Symmetric Semi-Positive Definite linear system whose right-hand side is perturbed by noise. In...
Finding Exact and Approximate Block Structures for ILU Preconditioning (2001)
Sparse matrices which arise in many applications often possess a block structure which can be exploited in iterative and direct solution methods. These block-matrices have as their entries small...
ARMS: An Algebraic Recursive Multilevel Solver for general sparse linear systems (2001)
This paper presents a general preconditioning method based on a multilevel partial solution approach. The basic step in constructing the preconditioner is to separate the initial points into two...
Enhanced Preconditioners for Large Sparse Least Squares Problems (2001)
Solving the normal equation systems arising from least-squares problems can be challenging because these systems are often very ill-conditioned. Though the use of iterative methods is appealing for...
On the relations between ILUs and factored approximate inverses (2001)
Matthias Bollhöfer, Yousef Saad
This paper discusses some relationships between Incomplete LU (ILU) factorization techniques and factored sparse approximate inverse (AINV) techniques. While ILU factorizations compute approximate LU...
Iterative Solution of Linear Systems in the 20th Century (2000)
This paper sketches the main research developments in the area of iterative methods for solving linear systems during the 20th century. Although iterative methods for solving linear systems find...
Iterative Solution of Linear Systems in the 20th Century (2000)
This paper sketches the main research developments in the area of iterative methods for solving linear systems during the 20th century. Although iterative methods for solving linear systems find...
Maria Sosonkina, John T. Melson, Yousef Saad, Layne T. Watson
In this paper, we consider linear systems arising in static tire equilibrium computation. The heterogeneous material properties, nonlinear constraints, and a 3D finite element formulation make the...
Iterative Solution of Linear Systems in the 20th Century (2000)
This paper sketches the main researchdevelopments in the area of iterative methods for solving linear systems during the 20th century. Although iterative methods for solving linear systems find their...
Iterative Solution of Linear Systems in the 20th Century (2000)
This paper sketches the main research developments in the area of iterative methods for solving linear systems during the 20th century. Although iterative methods for solving linear systems find...
James R. Chelikowsky, Yousef Saad, Serdar Ö˘güt, Igor Vasiliev, Andreas Stathopoulos
If the electronic structure of a given material is known, then many phys-ical and chemical properties can be accurately determined without resorting to experiment. However, determining the electronic...
ILUs and factorized approximate inverses are strongly related. Part I: Overview of results (2000)
Matthias Bollhofer, Yousef Saad
In an earlier paper we presented a few results which established some strong relations between incomplete factorization methods and factored approximate inversetype methods. In this paper some of...
Matthias Bollhöfer, Yousef Saad
In an earlier paper we presented a few results which established some strong relations between incomplete factorization methods and factored approximate inversetype methods. In this paper some of...
ILUs and Factorized Approximate Inverses are Strongly Related. Part I: Overview of Results (2000)
Matthias Bollhöfer, Yousef Saad
This paper discusses the relations between a broad class of incomplete LU factorization techniques and factorized sparse approximate inverse techniques based on computing triangular matrices Z; W...
Azzeddine Soulaimani, Yousef Saad, Ali Rebaine
This paper presents a nite element formulation for solving multidimensional compressible ows. This method is inspired by our experience with the SUPG, Finite Volume and Discontinuous-Galerkin...
James R. Chelikowsky, Yousef Saad, Serdar Ö˘güt, Igor Vasiliev, Andreas Stathopoulos
If the electronic structure of a given material is known, then many phys-ical and chemical properties can be accurately determined without resorting to experiment. However, determining the electronic...
James R. Chelikowsky, Yousef Saad, Serdar Ö˘güt, Igor Vasiliev, Andreas Stathopoulos
If the electronic structure of a given material is known, then many phys-ical and chemical properties can be accurately determined without resorting to experiment. However, determining the electronic...
Azzeddine Soulaimani, Nizar Ben Salah, Yousef Saad
Large CFD problems are often solved using iterative methods. Preconditioning is mandatory to accelerate the convergence of iterative methods. This paper presents new results using several...
Yousef Saad, Jun Zhang, Pii Sx
Abstract. We introduce block versions of the multielimination incomplete LU (ILUM) factorization preconditioning technique for solving general sparse unstructured linear systems. These...
Rational approximation preconditioners for general sparse linear systems (1999)
This paper presents a class of preconditioning techniques which exploit rational function approximations to the original matrix. The matrix is first shifted and then an incomplete LU factorization of...
Distributed Schur complement techniques for general sparse linear systems (1999)
This paper presents a few preconditioning techniques for solving general sparse linear systems on distributed memory environments. These techniques utilize the Schur complement system for deriving...
Non-Standard Parallel Solution Strategies for Distributed Sparse Linear Systems (1999)
. A number of techniques are described for solving sparse linear systems on parallel platforms. The general approach used is a domaindecomposition type method in which a processor is assigned a...
Enhanced Parallel Multicolor Preconditioning Techniques for Linear Systems (1999)
When solving a linear system in parallel, a large overhead in using an incomplete LU factorization as a preconditioner may annihilate any gains made from the improved convergence. This overhead is...
Block LU Preconditioners for Symmetric and Nonsymmetric Saddle Point Problems (1999)
Leigh Little Yousef, Leigh Little, Yousef Saad
In this paper, a block LU preconditioner for saddle point problems is presented. The main difference between the approach presented here and that of other studies is that an explicit, accurate...
Parallel Methods and Tools for Predicting Material Properties (1999)
Andreas Stathopoulos Serdar, Andreas Stathopoulos, Yousef Saad, James Chelikowsky, Hanchul Kim
Predicting the electronic structure of complex systems is an outstanding problem in materials science. If the electronic structure of a given material is known, then many physical and chemical...
ARMS: An Algebraic Recursive Multilevel Solver for general sparse linear systems (1999)
This paper presents a general preconditioning method based on a multilevel partial solution approach. The basic step in constructing the preconditioner is to separate the initial points into two...
Rational Approximation Preconditioners for General Sparse Linear Systems (1999)
Philippe Guillaume Yousef, Yousef Saad, Maria Sosonkina
This paper presents a class of preconditioning techniques which exploit rational function approximations to the original matrix. The matrix is first shifted and then an incomplete LU factorization of...
BILUTM: a domain-based multilevel block ILUT preconditioner for general sparse matrices (1999)
Abstract. This paper describes a domain-based multilevel block ILU preconditioner (BILUTM) for solving general sparse linear systems. This preconditioner combines a high accuracy incomplete LU...
BILUTM: a domain-based multilevel block ILUT preconditioner for general sparse matrices (1999)
Abstract. This paper describes a domain-based multilevel block ILU preconditioner (BILUTM) for solving general sparse linear systems. This preconditioner combines a high accuracy incomplete LU...
Inexact Newton Preconditioning Techniques for Eigenvalue Problems (1998)
Kesheng Wu, Yousef Saad, Andreas Stathopoulos
The focus of this paper is on numerical methods for finding a few eigenvalues and eigenvectors of a large sparse matrix. New preconditioning schemes are proposed for improving the effectiveness of a...
Domain Decomposition and Multi-Level Type Techniques for General Sparse Linear Systems (1998)
Yousef Saad, Maria Sosonkina, Jun Zhang
Domain-decomposition and multi-level techniques are often formulated for linear systems that arise from the solution of elliptic-type Partial Differential Equations. In this paper, generalizations of...
Modified Krylov acceleration for parallel environments (1998)
Caroline Le Calvez, Yousef Saad
This paper considers a few variants of Krylov subspace techniques for solving linear systems on parallel computers. The goal of these variants is to avoid global dotproducts which hamper parallelism...
BILUTM: A Domain-Based Multi-Level Block ILUT Preconditioner for General Sparse Matrices (1998)
Yousef Saad And, Yousef Saad, Jun Zhang
This paper describes a domain-based multi-level block ILU preconditioner (BILUTM) for solving general sparse linear systems. This preconditioner combines a high accuracy incomplete LU factorization...
Approximate Inverse Preconditioners Via Sparse-Sparse Iterations (1998)
. The standard incomplete LU (ILU) preconditioners often fail for general sparse indefinite matrices because they give rise to `unstable' factors L and U . In such cases, it may be attractive to...
Yousef Saad And, Yousef Saad, Jun Zhang
This paper introduces techniques based on diagonal threshold tolerance when developing multi-elimination and multi-level incomplete LU (ILUM) factorization preconditioners for solving general sparse...
Eigenvalue bounds from the Schur form (1998)
Thierry Braconnier Yousef, Yousef Saad
Computing the partial Schur form of a matrix is a common kernel in widely used software for solving eigenvalues problems. Partial Schur forms and Schur vectors also arise naturally in deflation...
A multi-level preconditioned iterative method based on a multi-level block ILU factorization preconditioning technique is introduced and is applied to the solution of unstructured sparse linear...
We introduce block versions of the multi-elimination incomplete LU (ILUM) factorization preconditioning technique for solving general sparse unstructured linear systems. These preconditioners have a...
BILUTM: A Domain-Based Multi-Level Block ILUT Preconditioner for General Sparse Matrices (1998)
This paper describes a domain-based multi-level block ILU preconditioner (BILUTM) for solving general sparse linear systems. This preconditioner combines a high accuracy incomplete LU factorization...
Enhanced Multi-Level Block ILU Preconditioning Strategies for General Sparse Linear Systems (1998)
This paper introduces several strategies to deal with pivot blocks in multi-level block incomplete LU factorization (BILUM) preconditioning techniques. These techniques are aimed at increasing the...
Inexact Newton Preconditioning Techniques for Eigenvalue Problems (1998)
Kesheng Wu, Yousef Saad, Andreas Stathopoulos
The focus of this paper is on numerical methods for finding a few eigenvalues and eigenvectors of a large sparse matrix. New preconditioning schemes are proposed for improving the effectiveness of a...
Inexact Newton preconditioning techniques for large symmetric eigenvalue problems (1998)
Kesheng Wu, Yousef Saad, Andreas Stathopoulos
The focus of this paper is on numerical methods for finding a few eigenvalues and eigenvectors of a large sparse matrix. New preconditioning schemes are proposed for improving the effectiveness of a...
PSPARSLIB Users Manual: A Portable Library of parallel Sparse Iterative Solvers (1998)
Yousef Saad, Gen-ching Lo, Sergey Kuznetsov
PSPARSLIB is a library of parallel iterative solvers. Its primary goal is to provide modules which can be used to simplify the development and implementation of sparse iterative solvers for...
This paper introduces techniques based on diagonal threshold tolerance when developing multi-elimination and multi-level incomplete LU (ILUM) factorization preconditioners for solving general sparse...
BILUTM: A Domain-Based Multi-Level Block ILUT Preconditioner for General Sparse Matrices (1998)
This paper describes a domain-based multi-level block ILU preconditioner (BILUTM) for solving general sparse linear systems. This preconditioner combines a high accuracy incomplete LU factorization...
Restarting techniques for (Jacobi-)Davidson symmetric eigenvalue methods (1998)
Andreas Stathopoulos, Yousef Saad
Abstract. The (Jacobi-)Davidson method, which is a popular preconditioned extension to the Arnoldi method for solving large eigenvalue problems, is often used with restarting. This has significant...
Robust Preconditioning for Sparse Linear Systems (1997)
Preconditioned iterative methods have become standard linear solvers in many applications, but their limited robustness in some cases has hindered the ability to efficiently solve very large problems...
Preconditioning the Matrix Exponential Operator with Applications (1997)
The idea of preconditioning is usually associated with solution techniques for solving linear systems or eigenvalue problems. It refers to a general method by which the original system is transformed...
Parallel Solution of General Sparse Linear Systems (1997)
Sergey Kuznetsov, Gen-ching Lo, Yousef Saad
. This paper discusses a few algorithms and their implementations for solving distributed general sparse linear systems. The preconditioners used are all variations of techniques originating from...
ILUS: An Incomplete LU Preconditioner in Sparse Skyline Format (1997)
Incomplete LU factorizations are among the most effective preconditioners for solving general large, sparse linear systems arising from practical engineering problems. This paper shows how an ILU...
Yousef Saad And, Yousef Saad, Jun Zhang
We introduce block versions of the multi-elimination incomplete LU (ILUM) factorization preconditioning technique for solving general sparse unstructured linear systems. These preconditioners have a...
Parallel Approximate Inverse Preconditioners (1997)
There has been much excitement recently over the use of approximate inverses for parallel preconditioning. The preconditioning operation is simply a matrix-vector product, and in the most popular...
Parallel Solution of General Sparse Linear Systems using PSPARSLIB (1997)
Yousef Saad, Sergey Kuznetsov, Gen-ching Lo
This paper describes some of the methods implemented in the package and examines a number of strategies used to improve their performance.
Experimental Study of ILU Preconditioners for Indefinite Matrices (1997)
Incomplete LU factorization preconditioners have been surprisingly successful for many cases of general nonsymmetric and indefinite matrices. However, their failure rate is still too high for them to...
. We introduce block versions of the multi-elimination incomplete LU (ILUM) factorization preconditioning technique for solving general sparse unstructured linear systems. These preconditioners have...
Domain Decomposition and Multi-Level Type Techniques for General Sparse Linear Systems (1997)
Yousef Saad, Maria Sosonkina, Jun Zhang
this paper, generalizations of these techniques for irregularly structured sparse linear systems are considered. An interesting common approach used to derive successful preconditioners is to resort...
Overlapping domain decomposition algorithms for general sparse matrices (1996)
Abstract. Domain decomposition methods for Finite Element problems using a partition based on the underlying finite element mesh have been extensively studied. In this paper, we discuss algebraic...
High order ILU preconditioners for CFD problems (1996)
Andrew Chapman Yousef, Andrew Chapman, Yousef Saad, Larry Wigton
This paper tests a number of ILU-type preconditioners for solving indefinite linear systems which arise from complex applications such as Computational Fluid Dynamics. Both point and block...
DQGMRES: a Direct Quasi-Minimal Residual Algorithm Based on Incomplete Orthogonalization (1996)
We describe a Krylov subspace technique, based on incomplete orthogonalization of the Krylov vectors, which can be considered as a truncated version of GMRES. Unlike GMRES(m), the restarted version...
Dynamic Thick Restarting of the Davidson, and the Implicitly Restarted Arnoldi Methods (1996)
Andreas Stathopoulos, Yousef Saad, Kesheng Wu
The Davidson method is a popular preconditioned variant of the Arnoldi method for solving large eigenvalue problems. For theoretical, as well as practical reasons the two methods are often used with...
Deflated and augmented Krylov subspace techniques (1996)
We present a general framework for a number of techniques based on projection methods on `augmented Krylov subspaces'. These methods include the deflated GMRES algorithm, an inner-outer FGMRES...
Iterative Solution of General Sparse Linear Systems on Clusters of Workstations (1996)
Solving sparse irregularly structured linear systems on parallel platforms poses several challenges. First, sparsity makes it difficult to exploit data locality and this is true for both distributed...
Iterative Solution of General Sparse Linear Systems on Clusters of Workstations (1996)
Solving sparse irregularly structured linear systems on parallel platforms poses several challenges. First, sparsity makes it difficult to exploit data locality and this is true for both distributed...
Although Domain Decomposition (DD) techniques constitute an important class of methods few actual general purpose codes based on these techniques have been developed so far. It is important to...
Analysis of Augmented Krylov Subspace Methods (1995)
Yousef Saad September, Yousef Saad
Residual norm estimates are derived for a general class of methods based on projection techniques on subspaces of the form Km + W, where Km is the standard Krylov subspace associated with the...
Approximate Inverse Techniques for Block-Partitioned Matrices (1995)
This paper proposes some preconditioning options when the system matrix is in block-partitioned form. This form may arise naturally, for example from the incompressible Navier-Stokes equations, or...
Andrei Malevsky September, Yousef Saad, Andrei V. Malevsky
Domain Decomposition techniques constitute an important class of methods which are especially appropriate in a parallel computing environment. However, few general purpose computational codes based...
A Schur Complement Method For Eigenvalue Problems (1995)
Andreas Stathopoulos, Yousef Saad, Charlotte F. Fischer
INTRODUCTION Domain decomposition algorithms have received much attention in the last decade [2]. The domain in which a differential equation is defined is partitioned in several subdomains, and the...
Preconditioned Krylov subspace methods for the numerical solution of Markov chains (1995)
In a general projection technique the original matrix problem of size N is approximated by one of dimension m, typically much smaller than N . A particularly successful class of techniques based on...
Tools and Libraries for Parallel Sparse Matrix Computations (1995)
Edmond Chow And, Edmond Chow, Yousef Saad
This paper describes two portable packages for general-purpose sparse matrix computations: SPARSKIT and P SPARSLIB. Their emphasis is on iterative techniques, with the latter also emphasizing...
Approximate Inverse Techniques for Block-Partitioned Matrices (1995)
This paper proposes some preconditioning options when the system matrix is in block-partitioned form. This form may arise naturally, for example from the incompressible Navier-Stokes equations, or...
Yousef Saad, Andrei V. Malevsky
. Domain Decomposition techniques constitute an important class of methods especially appropriate in a parallel computing environment, but only a few general purpose codes based on these techniques...
P-Sparslib: A Portable Library Of Distributed Memory Sparse Iterative Solvers (1995)
Yousef Saad, Andrei V. Malevsky
Domain Decomposition techniques constitute an important class of methods which are especially appropriate in a parallel computing environment. However, few general purpose computational codes based...
ILUS: An Incomplete LU Preconditioner in Sparse Skyline Format (1995)
Incomplete LU factorizations are among the most effective preconditioners for solving general large, sparse linear systems arising from practical engineering problems. This paper shows how an ILU...
Approximate Inverse Preconditioners for General Sparse Matrices (1994)
The standard Incomplete LU (ILU) preconditioners often fail for general sparse indefinite matrices because they give rise to `unstable' factors L and U . In such cases, it may be attractive to...
Robust Preconditioning of Large, Sparse, Symmetric Eigenvalue Problems (1994)
Andreas Stathopoulos, Yousef Saad, Charlotte. F. Fischer
Iterative methods for solving large, sparse, symmetric eigenvalue problems often encounter convergence difficulties because of ill-conditioning. The Generalized Davidson method is a well known...
Design of an iterative solution module for a parallel sparse matrix library (P SPARSLIB) (1994)
P SPARSLIB is a library of portable FORTRAN routines for parallel sparse matrix computations. The current thrust of the library is in iterative solution techniques. In this note we present the...
Theoretical Error Bounds and General Analysis of a few Lanczos-Type Algorithms (1994)
In this paper we give an overview of the results used to analyze some of the algorithms developed by Lanczos. These include the minimized iteration algorithm (conjugate gradient) for linear systems...
Numerical methods in Markov chain modeling (1989)
Philippe, Bernard, Saad, Yousef, Stewart, William
This paper describes and compares several methods for computing stationary probability distributions of Markov chains. The main linear algebra problem consists of computing an eigenvector of a...
Numerical methods in Markov chain modeling (1989)
Philippe, Bernard, Saad, Yousef, Stewart, William
This paper describes and compares several methods for computing stationary probability distributions of Markov chains. The main linear algebra problem consists of computing an eigenvector of a...
.
.
.
Experimental Study of ILU Preconditioners for Indefinite Matrices
Edmond Chow And, Edmond Chow, Yousef Saad
Incomplete LU factorization preconditioners have been surprisingly successful for many cases of general nonsymmetric and indefinite matrices. However, their failure rate is still too high for them to...
Preconditioned Krylov Subspace Methods for Eigenvalue Problems
Kesheng Wu, Yousef Saad, Andreas Stathopoulos
this paper we will explore several preconditioned eigenvalue solvers and identify the ones suited for finding large number of eigenvalues. Methods discussed in this paper make up the core of a...