The PageRank Problem

The thesis is the result of a bachelor research project about Google's PageRank. An analysis of the hyperlink structure of the World Wide Web is made and a model for web surfing studied. Based on this model, some standard methods to compute the PageRank of web pages is investigated. Special attention is given to computing PageRanks by using...

Efficient Iterative Solution of Large Linear Systems on Heterogeneous Computing Systems

This dissertation deals mainly with the design, implementation, and analysis of efficient iterative solution methods for large sparse linear systems on distributed and heterogeneous computing systems as found in Grid computing. First, a case study is performed on iteratively solving large symmetric linear systems on both a multi–cluster and a...

On the Convergence Behavior of IDR(s) and Related Methods

An explanation is given of the convergence behavior of IDR(s) methods. The convergence mechanism of these algorithms has two components. The first consists of damping properties of certain factors in the residual polynomials, which becomes less important for large values of s. The second component depends on the behavior of Lanczos polynomials...

The effect of group decisions in heat transitions: An agent-based approach

The Netherlands aims at reducing natural gas consumption for heating in the housing sector. Although homeowners are responsible for replacing their heating systems and improving dwelling insulation, they are not always able to make individual decisions. Some projects require group decisions within and between buildings. We use an agent-based...

An MSSS-preconditioned matrix equation approach for the time-harmonic elastic wave equation at multiple frequencies

In this work, we present a new numerical framework for the efficient solution of the time-harmonic elastic wave equation at multiple frequencies. We show that multiple frequencies (and multiple right-hand sides) can be incorporated when the discretized problem is written as a matrix equation. This matrix equation can be solved efficiently...

Iterative solutions to sequences of Helmholtz equations

We consider sequences of linear systems of equations that follow from the differential equations that describe the acoustics of a car, where the solution to a single linear system corresponds to the pressure perturbations that are caused by acoustic waves of a certain frequency. We consider several iterative numerical methods which belong to the...

PIDR(s): IDR(s) as a Projection Method

The Induced Dimension Reduction(s) method (or the IDR(s) method) is an example of an iterative method used for solving systems of linear equations. Projection methods are a special type of iterative method. They find an approximate solution in a subspace (the right subspace) by requiring that the residual is orthogonal to another subspace (the...

Exploiting the flexibility of IDR(s) for grid computing

The IDR(s) method that is proposed in [26] is an efficient limited memory method for solving large nonsymmetric systems of linear equations. In [11] an IDR(s) variant is described that has a single synchronisation point per iteration step, which makes this variant well-suited for parallel and grid computing. In this paper, we combine this IDR(s)...

Interpreting IDR(s) as a deflation method

In this paper the IDR(s) method is interpreted in the context of deflation methods. It is shown that IDR(s) can be seen as a Richardson iteration preconditioned by a variable deflation–type preconditioner. The main result of this paper is the IDR projection theorem, which relates the spectrum of the deflated system in each IDR(s) cycle to all...

Nested Krylov methods for shifted linear systems

On the convergence behaviour of IDR(s)

An explanation is given of the convergence behaviour of the IDR(s) methods. The convergence of the IDR(s) algorithms has two components. The first consists of damping properties of certain factors in the residual polynomials, which becomes less important for large values of s. The second component depends on the behaviour of quasi-Lanczos...

Flexible and multi-shift induced dimension reduction algorithms for solving large sparse linear systems

We give two important generalizations of the Induced Dimension Reduction (IDR) approach for the solution of linear systems. We derive a flexible and a multi-shift Quasi-Minimal Residual IDR (QMRIDR) variant. Numerical examples are presented to show the effectiveness of these new IDR variants compared to existing ones and to other Krylov subspace...

An elegant IDR(s) variant that efficiently exploits bi-orthogonality properties

The IDR(s) method that is proposed in [18] is a very efficient limited memory method for solving large nonsymmetric systems of linear equations. IDR(s) is based on the induced dimension reduction theorem, that provides a way to construct subsequent residuals that lie in a sequence of shrinking subspaces. The IDR(s) algorithm that is given in [18...

On the statistical properties of solutions of completely random linear systems

In this report the probability distributions of x and kxk are derived, where x is the solution of a finite square, completely random linear system, i.e. a system Ax = b, of which all entries are stochastically independent, and standard Gaussian distributed stochastic variables. The question on the statistical behaviour of kxk came up in [5], the...

Fast solution of nonsymmetric linear systems on Grid computers using parallel variants of IDR(s)

IDR(s) is a family of fast algorithms for iteratively solving large nonsymmetric linear systems [14]. With cluster computing and in particular with Grid computing, the inner product is a bottleneck operation. In this paper, three techniques are combined in order to alleviate this bottleneck. Firstly, the efficient and stable IDR(s) algorithm...