WEIGHTED MATRIX ORDERING AND PARALLEL BANDED PRECONDITIONERS FOR ITERATIVE LINEAR SYSTEM SOLVERS

Download
2010-01-01
Manguoğlu, Murat
Sameh, Ahmed H.
Grama, Ananth
The emergence of multicore architectures and highly scalable platforms motivates the development of novel algorithms and techniques that emphasize concurrency and are tolerant of deep memory hierarchies, as opposed to minimizing raw FLOP counts. While direct solvers are reliable, they are often slow and memory-intensive for large problems. Iterative solvers, on the other hand, are more efficient but, in the absence of robust preconditioners, lack reliability. While preconditioners based on incomplete factorizations ( whenever they exist) are effective for many problems, their parallel scalability is generally limited. In this paper, we advocate the use of banded preconditioners instead and introduce a reordering strategy that enables their extraction. In contrast to traditional bandwidth reduction techniques, our reordering strategy takes into account the magnitude of the matrix entries, bringing the heaviest elements closer to the diagonal, thus enabling the use of banded preconditioners. When used with effective banded solvers-in our case, the Spike solver-we show that banded preconditioners (i) are more robust compared to the broad class of incomplete factorization-based preconditioners, (ii) deliver higher processor performance, resulting in faster time to solution, and (iii) scale to larger parallel configurations. We demonstrate these results experimentally on a large class of problems selected from diverse application domains.
SIAM JOURNAL ON SCIENTIFIC COMPUTING

Suggestions

Estimation in bivariate nonnormal distributions with stochastic variance functions
Tiku, Moti L.; İslam, Muhammed Qamarul; SAZAK, HAKAN SAVAŞ (Elsevier BV, 2008-01-01)
Data sets in numerous areas of application can be modelled by symmetric bivariate nonnormal distributions. Estimation of parameters in such situations is considered when the mean and variance of one variable is a linear and a positive function of the other variable. This is typically true of bivariate t distribution. The resulting estimators are found to be remarkably efficient. Hypothesis testing procedures are developed and shown to be robust and powerful. Real life examples are given.
Joint linear complexity of multisequences consisting of linear recurring sequences
Fu, Fang-Wei; Niederreiter, Harald; Özbudak, Ferruh (Springer Science and Business Media LLC, 2009-04-01)
The linear complexity of sequences is one of the important security measures for stream cipher systems. Recently, in the study of vectorized stream cipher systems, the joint linear complexity of multisequences has been investigated. In this paper, we study the joint linear complexity of multisequences consisting of linear recurring sequences. The expectation and variance of the joint linear complexity of random multisequences consisting of linear recurring sequences are determined. These results extend the ...
Derivative free multilevel optimization methods
Pekmen, Bengisen; Karasözen, Bülent; Department of Scientific Computing (2009)
Derivative free optimization algorithms are implementations of trust region based derivative-free methods using multivariate polynomial interpolation. These are designed to minimize smooth functions whose derivatives are not available or costly to compute. The trust region based multilevel optimization algorithms for solving large scale unconstrained optimization problems resulting by discretization of partial differential equations (PDEs), make use of different discretization levels to reduce the computati...
CLUSTER ALGEBRAS AND SEMIPOSITIVE SYMMETRIZABLE MATRICES
Seven, Ahmet İrfan (American Mathematical Society (AMS), 2011-05-01)
There is a particular analogy between combinatorial aspects of cluster algebras and Kac-Moody algebras: roughly speaking, cluster algebras are associated with skew-symmetrizable matrices while Kac-Moody algebras correspond to (symmetrizable) generalized Cartan matrices. Both classes of algebras and the associated matrices have the same classification of finite type objects by the well-known Cartan-Killing types. In this paper, we study an extension of this correspondence to the affine type. In particular, w...
Implicit motif distribution based hybrid computational kernel for sequence classification
Atalay, Mehmet Volkan (Oxford University Press (OUP), 2005-04-15)
Motivation: We designed a general computational kernel for classification problems that require specific motif extraction and search from sequences. Instead of searching for explicit motifs, our approach finds the distribution of implicit motifs and uses as a feature for classification. Implicit motif distribution approach may be used as modus operandi for bioinformatics problems that require specific motif extraction and search, which is otherwise computationally prohibitive.
Citation Formats
M. Manguoğlu, A. H. Sameh, and A. Grama, “WEIGHTED MATRIX ORDERING AND PARALLEL BANDED PRECONDITIONERS FOR ITERATIVE LINEAR SYSTEM SOLVERS,” SIAM JOURNAL ON SCIENTIFIC COMPUTING, pp. 1201–1216, 2010, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/36460.