The optimal preconditioner cU (A) of a given matrix A was proposed in 1988 by T. Chan [6]. Since then, it has been proved to be efficient for solving a large class of structured systems. In this paper, we construct th...
详细信息
The optimal preconditioner cU (A) of a given matrix A was proposed in 1988 by T. Chan [6]. Since then, it has been proved to be efficient for solving a large class of structured systems. In this paper, we construct the optimal preconditioners for different functions of matrices. More precisely, let f be a function of matrices from CnXn to C-nXn. Given A is an element of C-nxn, there are two possible optimal preconditioners for f (A): cu ( f (A)) and f (cu (A)). In the paper, we study properties of both cu (f (A)) and f (cu (A)) for different functions of matrices. Numerical experiments are given to illustrate the efficiency of the optimal preconditioners when they are used to solve f (A)x = b. (C) 2014 Elsevier Inc. All rights reserved.
For any given matrix A ∈ℂnxn, a preconditioner tU(A) called the superoptimal preconditioner was proposed in 1992 by Tyrtyshnikov. It has been shown that tU(A) is an efficient preconditioner for solving various struct...
详细信息
For any given matrix A ∈ℂnxn, a preconditioner tU(A) called the superoptimal preconditioner was proposed in 1992 by Tyrtyshnikov. It has been shown that tU(A) is an efficient preconditioner for solving various structured systems, for instance, Toeplitz-like systems. In this paper, we construct the superoptimal preconditioners for different functions of matrices. Let f be a function of matrices from ℂnxn to ℂnxn. For any A ∈ ℂ nxn, one may construct two superoptimal preconditioners for f(A): tU(f(A)) and f(tU(A)). We establish basic properties of tU(f(A)) and f(tU(A)) for different functions of matrices. Some numerical tests demonstrate that the proposed preconditioners are very efficient for solving the system f(A)x = b. [ABSTRACT FROM AUTHOR]
Most of the controllers designed for systems with timedelays involve finite impulse response (FIR) filters in their structure, in particular prediction based controllers for systems with input/output delays. We presen...
详细信息
Most of the controllers designed for systems with timedelays involve finite impulse response (FIR) filters in their structure, in particular prediction based controllers for systems with input/output delays. We present theory, algorithms and software to evaluate the frequency response, to approximate the filters by stable linear timeinvariant systems and to compute their induced L-2 gain. The approach is based on the theory of functions of matrices. In the approach pole zero cancelations in frequency domain representations are explicitly taken into account.
An inequality is proved for convex functions applied to self-adjoint matrices, Several known inequalities are shown to be consequences, but properly weaker. (C) 2001 Elsevier Science Inc. All rights reserved.
An inequality is proved for convex functions applied to self-adjoint matrices, Several known inequalities are shown to be consequences, but properly weaker. (C) 2001 Elsevier Science Inc. All rights reserved.
The paper deals with Krylov methods for approximating functions of matrices via interpolation. In this frame residual smoothing techniques based on quasi-kemel polynomials are considered. Theoretical results as well a...
详细信息
The paper deals with Krylov methods for approximating functions of matrices via interpolation. In this frame residual smoothing techniques based on quasi-kemel polynomials are considered. Theoretical results as well as nurnerical experiments illustrate the effectiveness of our approach. Copyright 0 2004 John Wiley & Sons, Ltd.
Let A be an s-sparse Hermitian matrix, f(x) be a univariate function, and i, j be two indices. In this work, we investigate the query complexity of approximating . We show that for any continuous function f(x):[-1,1]-...
详细信息
ISBN:
(纸本)9798400703836
Let A be an s-sparse Hermitian matrix, f(x) be a univariate function, and i, j be two indices. In this work, we investigate the query complexity of approximating < i vertical bar f(A)vertical bar j >. We show that for any continuous function f(x):[-1,1]-> [-1,1], the quantum query complexity of computing < i vertical bar f(A)vertical bar j > +/- epsilon/4 is lower bounded by Omega((deg) over tilde (epsilon)(f)). The upper bound is at most quadratic in (deg) over tilde (epsilon)(f) and is linear in (deg) over tilde (epsilon)(f) under certain mild assumptions on A. Here the approximate degree (deg) over tilde (epsilon)(f) is the minimum degree such that there is a polynomial of that degree approximating f up to additive error epsilon in the interval [-1,1]. We also show that the classical query complexity is lower bounded by (Omega) over tilde (epsilon)((s/2)(((deg) over tilde2 epsilon(f)-1)/6)) for any s >= 4. Our results show that the quantum and classical separation is exponential for any continuous function of sparse Hermitian matrices, and also imply the optimality of implementing smooth functions of sparse Hermitian matrices by quantum singular value transformation. The main techniques we used are the dual polynomial method for functions over the reals, linear semi-infinite programming, and tridiagonal matrices.
作者：
Hon, SeanUniv Oxford
Math Inst Radcliffe Observ Quarter Oxford OX2 6GG England
We propose several circulant preconditioners for systems defined by some functions g of Toeplitz matrices A(n). In this paper we are interested in solving g(A(n))x = b by the preconditioned conjugate method or the pre...
详细信息
We propose several circulant preconditioners for systems defined by some functions g of Toeplitz matrices A(n). In this paper we are interested in solving g(A(n))x = b by the preconditioned conjugate method or the preconditioned minimal residual method, namely in the cases when g(x) are the functions e(z), sin z and cos z. Numerical results are given to show the effectiveness of the proposed preconditioners. (C) 2018 Elsevier Inc. All rights reserved.
Circulant preconditioning for symmetric Toeplitz systems has been well developed over the past few decades. For a large class of such systems, descriptive bounds on convergence for the conjugate gradient method can be...
详细信息
Circulant preconditioning for symmetric Toeplitz systems has been well developed over the past few decades. For a large class of such systems, descriptive bounds on convergence for the conjugate gradient method can be obtained. For (real) nonsymmetric Toeplitz systems, much work had been focused on normalising the original systems until Pestana and Wathen (Siam J. Matrix Anal. Appl. 36(1):273-288 2015) recently showed that theoretic guarantees on convergence for the minimal residual method can be established via the simple use of reordering. The authors further proved that a suitable absolute value circulant preconditioner can be used to ensure rapid convergence. In this paper, we show that the related ideas can also be applied to the systems defined by analytic functions of (real) nonsymmetric Toeplitz matrices. For the systems defined by analytic functions of complex Toeplitz matrices, we also show that certain circulant preconditioners are effective. Numerical examples with the conjugate gradient method and the minimal residual method are given to support our theoretical results.
The aim of this work is to develop a fast algorithm for approximating the matrix function f (A) of a square matrix A that is symmetric and has hierarchically semiseparable (HSS) structure. Appearing in a wide variety ...
详细信息
The aim of this work is to develop a fast algorithm for approximating the matrix function f (A) of a square matrix A that is symmetric and has hierarchically semiseparable (HSS) structure. Appearing in a wide variety of applications, often in the context of discretized (fractional) differential and integral operators, HSS matrices have a number of attractive properties facilitating the development of fast algorithms. In this work, we use an unconventional telescopic decomposition of A, inspired by recent work of Levitt and Martinsson on approximating an HSS matrix from matrixvector products with a few random vectors. This telescopic decomposition allows us to approximate f (A) by recursively performing low-rank updates with rational Krylov subspaces while keeping the size of the matrices involved in the rational Krylov subspaces small. In particular, no large-scale linear system needs to be solved, which yields favorable complexity estimates and reduced execution times compared to existing methods, including an existing divide-and-conquer strategy. The advantages of our newly proposed algorithms are demonstrated for a number of examples from the literature, featuring the exponential, the inverse square root, and the sign function of a matrix. For the special case of matrix inversion, our algorithm reduces to a procedure previously proposed by Gillman, Young, and Martinsson [Front. Math. China, 7 (2012), pp. 217--247].
In this paper we present an eigenvalue decomposition for any real symmetric tridiagonal 2-Toeplitz matrix of odd order, where the eigenvector matrix is orthogonal. Using this decomposition we study the entries of cont...
详细信息
In this paper we present an eigenvalue decomposition for any real symmetric tridiagonal 2-Toeplitz matrix of odd order, where the eigenvector matrix is orthogonal. Using this decomposition we study the entries of continuous functions of large real symmetric tridiagonal 2-Toeplitz matrices. Furthermore, we also study in the present paper the entries of continuous functions of large Hermitian Toeplitz matrices with at most three non-zero diagonals. (C) 2013 Elsevier Inc. All rights reserved.
暂无评论