Iterative Methods and Partitioning Techniques for Large Sparse Problems in Network Analysis Open Access
Kuhlemann, Verena (2012)
Abstract
The analysis of networks is an important aspect in many fields.
Here we consider three different topics: the numerical solution of
Markov chains, ranking of genes, and parallel computations with
large scale-free graphs.
First, additive Schwarz methods are a class of domain decomposition
methods that are suitable for the solution of large linear systems
in serial as well as in parallel mode. We adapt the Restricted
Additive Schwarz (RAS) method to the computation of the stationary
probability distribution vector of large, sparse, irreducible
stochastic matrices. The convergence properties are analyzed and
extensive numerical experiments aimed at assessing the effect of
varying the number of subdomains and the choice of overlap are
discussed.
Next, the ranking of genes plays an important role in the
identification of key genes for a specific disease. A modification
of the PageRank algorithm that is used to rank web pages is the
GeneRank algorithm. We assessed the performance of additive Schwarz
methods as well as that of Chebyshev iteration for the solution of
the GeneRank problem.
Finally, many large networks are scale-free. That is, the degree
distribution follows a power-law. Currently available graph
partitioners are not efficient for such an irregular degree
distribution. The lack of a good partitioning leads to excessive
inter-processor communication requirements during each
matrix-vector product on parallel distributed-memory computers. We
present an approach to alleviate this problem based on embedding
the original irregular graph into a more regular one by
disaggregating (splitting up) vertices in the original graph. Even
though the latter graph is larger, we are able to decrease the
communication requirements considerably and improve the performance
of the matrix-vector product.
Table of Contents
- Introduction and preliminaries
- Restricted Additive Schwarz Methods for Markov Chains
- Iterative solvers for the GeneRank problem
- Disaggregation techniques for large scale-free graphs
- Conclusions and suggestions for future work
About this Dissertation
| School | |
|---|---|
| Department | |
| Degree | |
| Submission | |
| Language |
|
| Research Field | |
| Keyword | |
| Committee Chair / Thesis Advisor | |
| Committee Members |
Primary PDF
| Thumbnail | Title | Date Uploaded | Actions |
|---|---|---|---|
|
|
Iterative Methods and Partitioning Techniques for Large Sparse Problems in Network Analysis () | 2018-08-28 13:55:29 -0400 |
|
Supplemental Files
| Thumbnail | Title | Date Uploaded | Actions |
|---|