Comparison of eigensolvers for symmetric band matrices.

We compare different algorithms for computing eigenvalues and eigenvectors of a symmetric band matrix across a wide range of synthetic test problems. Of particular interest is a comparison of state-of-the-art tridiagonalization-based methods as implemented in Lapack or Plasma on the one hand, and the block divide-and-conquer (BD&C) algorithm as well as the block twisted factorization (BTF) method on the other hand. The BD&C algorithm does not require tridiagonalization of the original band matrix at all, and the current version of the BTF method tridiagonalizes the original band matrix only for computing the eigenvalues. Avoiding the tridiagonalization process sidesteps the cost of backtransformation of the eigenvectors. Beyond that, we discovered another disadvantage of the backtransformation process for band matrices: In several scenarios, a lot of gradual underflow is observed in the (optional) accumulation of the transformation matrix and in the (obligatory) backtransformation step. According to the IEEE 754 standard for floating-point arithmetic, this implies many operations with subnormal (denormalized) numbers, which causes severe slowdowns compared to the other algorithms without backtransformation of the eigenvectors. We illustrate that in these cases the performance of existing methods from Lapack and Plasma reaches a competitive level only if subnormal numbers are disabled (and thus the IEEE standard is violated). Overall, our performance studies illustrate that if the problem size is large enough relative to the bandwidth, BD&C tends to achieve the highest performance of all methods if the spectrum to be computed is clustered. For test problems with well separated eigenvalues, the BTF method tends to become the fastest algorithm with growing problem size.

Static vs. mobile sink: The influence of basic parameters on energy efficiency in wireless sensor networks.

Over the last decade a large number of routing protocols has been designed for achieving energy efficiency in data collecting wireless sensor networks. The drawbacks of using a static sink are well known. It has been argued in the literature that a mobile sink may improve the energy dissipation compared to a static one. Some authors focus on minimizing Emax, the maximum energy dissipation of any single node in the network, while others aim at minimizing Ebar, the average energy dissipation over all nodes. In our paper we take a more holistic view, considering both Emax and Ebar. The main contribution of this paper is to provide a simulation-based analysis of the energy efficiency of WSNs with static and mobile sinks. The focus is on two important configuration parameters: mobility path of the sink and duty cycling value of the nodes. On the one hand, it is well known that in the case of a mobile sink with fixed trajectory the choice of the mobility path influences energy efficiency. On the other hand, in some types of applications sensor nodes spend a rather large fraction of their total lifetime in idle mode, and therefore higher energy efficiency can be achieved by using the concept of reduced duty cycles. In particular, we quantitatively analyze the influence of duty cycling and the mobility radius of the sink as well as their interrelationship in terms of energy consumption for a well-defined model scenario. The analysis starts from general load considerations and is refined into a geometrical model. This model is validated by simulations which are more realistic in terms of duty cycling than previous work. It is illustrated that over all possible configuration scenarios in terms of duty cycle and mobility radius of the sink the energy dissipation in the WSN can vary up to a factor of nine in terms of Emax and up to a factor of 17 in terms of Ebar. It turns out that in general the choice of the duty cycle value is more important for achieving energy efficiency than the choice of the mobility radius of the sink. Moreover, for small values of the duty cycle, a static sink turns out to be optimal in terms of both Emax and Ebar. For larger values of the duty cycle, a mobile sink has advantages over a static sink, especially in terms of Emax. These insights into the basic interrelationship between duty cycle value and mobility radius of a mobile sink are relevant for energy efficient operation of homogeneous WSNs beyond our model scenario.

Scalable and fault tolerant orthogonalization based on randomized distributed data aggregation.

The construction of distributed algorithms for matrix computations built on top of distributed data aggregation algorithms with randomized communication schedules is investigated. For this purpose, a new aggregation algorithm for summing or averaging distributed values, the push-flow algorithm, is developed, which achieves superior resilience properties with respect to failures compared to existing aggregation methods. It is illustrated that on a hypercube topology it asymptotically requires the same number of iterations as the optimal all-to-all reduction operation and that it scales well with the number of nodes. Orthogonalization is studied as a prototypical matrix computation task. A new fault tolerant distributed orthogonalization method rdmGS, which can produce accurate results even in the presence of node failures, is built on top of distributed data aggregation algorithms.

Computing eigenvectors of block tridiagonal matrices based on twisted block factorizations.

New methods for computing eigenvectors of symmetric block tridiagonal matrices based on twisted block factorizations are explored. The relation of the block where two twisted factorizations meet to an eigenvector of the block tridiagonal matrix is reviewed. Based on this, several new algorithmic strategies for computing the eigenvector efficiently are motivated and designed. The underlying idea is to determine a good starting vector for an inverse iteration process from the twisted block factorizations such that a good eigenvector approximation can be computed with a single step of inverse iteration. An implementation of the new algorithms is presented and experimental data for runtime behaviour and numerical accuracy based on a wide range of test cases are summarized. Compared with competing state-of-the-art tridiagonalization-based methods, the algorithms proposed here show strong reductions in runtime, especially for very large matrices and/or small bandwidths. The residuals of the computed eigenvectors are in general comparable with state-of-the-art methods. In some cases, especially for strongly clustered eigenvalues, a loss in orthogonality of some eigenvectors is observed. This is not surprising, and future work will focus on investigating ways for improving these cases.