1,720,979 research outputs found
Matrix Structures and Matrix Functions
No full textStructured matrices play a relevant role in symbolic and numerical computations. In the literature and in applications we encounter several types of structure, which are typically related to the properties of the problems they stem from: banded structure is often associated with locality of functions or operators, Toeplitz structure arises from shift invariance properties, off-diagonal low-rank structure appears in inverses of banded matrices.A common trait of most matrix structures is the availability of fast algorithms that perform fundamental operations, such as matrix-vector or matrix-matrix multiplication, solution of linear systems, or eigenvalue computation. For problems of large size, such algorithms are extremely useful both from a symbolic and a numeric point of view, although of course in a numerical setting one needs to pay attention to possible stability issues.The tutorial will start with a brief overview of matrix structures and of their properties: we are especially interested here in rank structures and in certain forms of sparsity. We will then focus on selected topics concerning the analysis and computation of functions of structured matrices. Functions of matrices have a wide range of applications, for which we will give several examples, from the solution of differential equations to network analysis. Think for instance of the matrix exponential exp(A): it appears in the solution of a multidimensional Cauchy problem with coefficient matrix A, but it also has a combinatorial meaning when A is the adjacency matrix of a graph. If the quantity of interest is the action of a matrix function on a vector, moreover, one can often bypass the explicit construction of the matrix function itself and devise a more efficient approach.Most methods for the computation of matrix functions are ultimately based on polynomial or rational approximation, which are either applied in explicit form, or through iterative methods such as Lanczos or Arnoldi, often in combination with suitable pre- and post-processing steps. If matrix A is structured, it is natural to ask how to tailor such methods to the specific structure of A. We will present a few possible answers to this question and demonstrate their advantages through several practical examples
Fast computation of yearly averages of useful quantities for solar engineering
No full textIn solar engineering, many simulations require the computation of averages over a year of quantities such as the efficiency of solar plants. In the case of stationary quantities, i.e., that do not depend on the past history but only on the present conditions, time averages can be replaced by averages over the solar position, which are much faster to compute. Through a suitable choice of coordinates for the Sun position, namely, the hour angle and a declination-equivalent coordinate, the problem can be rewritten as a comparatively simple expression involving the sum of two double integrals; the solution can then be obtained numerically via suitable fast quadrature methods. The average over a year can be computed by transforming the dependence on irradiation, cloudiness, temperature or other instantaneous parameters into two dependences on Sun position – one for winter-spring (ascending declination) and one for summer-winter (descending declination). The proposed method is substantially faster than usual time integration over a year: the speedup factor ranges from 18 to almost 700 in the considered examples. It is especially well-suited to computations that require many yearly averages and could even be unfeasible otherwise. Examples of such applications include multi-parameter optimisations of the configuration of a power plant with the goal of maximizing the overall year production
Computation of quasiseparable representations of Green matrices
No full textThe well-known Asplund theorem states that the inverse of a (possibly one-sided) band matrix A is a Green matrix. In accordance with quasiseparable theory, such a matrix admits a quasiseparable representation in its rank-structured part. Based on this idea, we derive algorithms that compute a quasiseparable representation of A−1 with linear complexity. Many inversion algorithms for band matrices exist in the literature. However, algorithms based on a computation of the rank structure performed theoretically via the Asplund theorem appear for the first time in this paper. Numerical experiments confirm complexity estimates and offer insight into stability properties
Do we really need a seasonal energy storage? Results for photovoltaic technology in an unfavourable scenario
Full text linkEnergy storage systems play a crucial role in the transition to renewable energy. Short-term storage (STS), e.g., batteries, has a capacity of a few hours, meant to compensate the energy deficit due to day-night cycle or short-term fluctuations. Long-term storage (LTS), e.g., renewable fuels, can compensate seasonal variations. The importance of STS is undisputed; the need for LTS is much more debated. Here we compare two photovoltaic systems, one (A) endowed only with STS, and another (B) equipped also with unlimited LTS, in a scenario unfavourable to (A) because of high seasonal variability of irradiation and high heating load in winter. We show that (A) requires only a moderate oversize of the peak power (about 20%) w.r.t. (B) when both systems are sized to supply 85% of the whole electrifiable load, which includes domestic heating and transport. Therefore, the current lack of clear routes towards grid-scale LTS should not be considered as a reason to delay the transition to renewables
Implicit QR for Companion-like Pencils
Full text linkA fast implicit QR algorithm for eigenvalue computation of low rank corrections of unitary matrices is adjusted to work with matrix pencils arising from polynomial zerofinding problems . The modified QZ algorithm computes the generalized eigenvalues of certain NxN rank structured matrix pencils using O(N^2) ops and O(N) memory storage. Numerical experiments and comparisons confirm the effectiveness and the stability of the proposed method
Ranking nodes in directed networks via continuous-time quantum walks
Full text linkFour new centrality measures for directed networks based on unitary, continuous-time quantum walks (CTQW) in n dimensions—where n is the number of nodes—are presented, tested and discussed. The main idea behind these methods consists in re-casting the classical HITS and PageRank algorithms as eigenvector problems for symmetric matrices, and using these symmetric matrices as Hamiltonians for CTQWs, in order to obtain a unitary evolution operator. The choice of the initial state is also crucial. Two options were tested: a vector with uniform occupation and a vector weighted w.r.t. in- or out-degrees (for authority and hub centrality, respectively). Two methods are based on a HITS-derived Hamiltonian, and two use a PageRank-derived Hamiltonian. Centrality scores for the nodes are defined as the average occupation values. All the methods have been tested on a set of small, simple graphs in order to spot possible evident drawbacks, and then on a larger number of artificially generated larger-sized graphs, in order to draw a comparison with classical HITS and PageRank. Numerical results show that, despite some pathologies found in three of the methods when analyzing small graphs, all the methods are effective in finding the first and top ten nodes in larger graphs. We comment on the results and offer some insight into the good accordance between classical and quantum approaches
A contour integral approach to the computation of invariant pairs
Full text linkWe study some aspects of the invariant pair problem for matrix polynomials, as introduced by Betcke and Kressner [3] and by Beyn and Thümmler [6]. Invariant pairs extend the notion of eigenvalue–eigenvector pairs, providing a counterpart of invariant subspaces for the nonlinear case. We compute formulations for the condition numbers and the backward error for invariant pairs and solvents. We then adapt the Sakurai–Sugiura moment method [1] to the computation of invariant pairs, including some classes of problems that have multiple eigenvalues. Numerical refinement via a variant of Newton's method is also studied. Furthermore, we investigate the relation between the matrix solvent problem and the triangularization of matrix polynomials
Matrix functions in network analysis
Full text linkWe review the recent use of functions of matrices in the analysis of graphs and networks, with special focus on centrality and communicability measures and diffusion processes. Both undirected and directed networks are considered, as well as dynamic (temporal) networks. Computational issues are also addressed
Quantum hub and authority centrality measures for directed networks based on continuous-time quantum walks
No full textIn this article, we introduce, test and discuss three quantum methods for computing hub and authority centrality scores in directed networks. The methods are based on unitary, continuous-time quantum walks; the construction of a suitable Hermitian Hamiltonian is achieved by performing a quantum walk on the associated bipartite graph. Two methods, called CQAu and CQAw, use the same evolution operator, inspired by the classical Hyperlink-Induced Topic Search (HITS) algorithm, but with different initial states; the computation of hub and authority scores is performed simultaneously. The third method, called CQG and inspired by classical PageRank, requires instead two separate runs with different evolution operators, one for hub and one for authority scores. The methods are tested on several directed graphs with different sizes and properties; a comparison with other well-established ranking algorithms is provided. CQAw emerges as the most reliable of the three methods and yields rankings that are largely compatible with results from HITS, although CQAu and CQG also present interesting features and potential for applications
- …
