首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 171 毫秒
1.
This article studies the unstructured and structured backward error analysis of specified eigenpairs for matrix polynomials. The structures we discuss include T $$ T $$ -symmetric, T $$ T $$ -skew-symmetric, Hermitian, skew Hermitian, T $$ T $$ -even, T $$ T $$ -odd, H $$ H $$ -even, H $$ H $$ -odd, T $$ T $$ -palindromic, T $$ T $$ -anti-palindromic, H $$ H $$ -palindromic, and H $$ H $$ -anti-palindromic matrix polynomials. Minimally structured perturbations are constructed with respect to Frobenius norm such that specified eigenpairs become exact eigenpairs of an appropriately perturbed matrix polynomial that also preserves sparsity. Further, we have used our results to solve various quadratic inverse eigenvalue problems that arise from real-life applications.  相似文献   

2.
Standard rank-revealing factorizations such as the singular value decomposition (SVD) and column pivoted QR factorization are challenging to implement efficiently on a GPU. A major difficulty in this regard is the inability of standard algorithms to cast most operations in terms of the Level-3 BLAS. This article presents two alternative algorithms for computing a rank-revealing factorization of the form A = U T V $$ \mathbf{\mathsf{A}}=\mathbf{\mathsf{UT}}{\mathbf{\mathsf{V}}}^{\ast } $$ , where U $$ \mathbf{\mathsf{U}} $$ and V $$ \mathbf{\mathsf{V}} $$ are orthogonal and T $$ \mathbf{\mathsf{T}} $$ is trapezoidal (or triangular if A $$ \mathbf{\mathsf{A}} $$ is square). Both algorithms use randomized projection techniques to cast most of the flops in terms of matrix-matrix multiplication, which is exceptionally efficient on the GPU. Numerical experiments illustrate that these algorithms achieve significant acceleration over finely tuned GPU implementations of the SVD while providing low rank approximation errors close to that of the SVD.  相似文献   

3.
The present work is devoted to the construction of an asymptotic expansion for the eigenvalues of a Toeplitz matrix T n ( a ) $$ {T}_n(a) $$ as n $$ n $$ goes to infinity, with a continuous and real-valued symbol a $$ a $$ having a power singularity of degree γ $$ \gamma $$ with 1 < γ < 2 $$ 1<\gamma <2 $$ , at one point. The resulting matrix is dense and its entries decrease slowly to zero when moving away from the main diagonal, we apply the so called simple-loop (SL) method for constructing and justifying a uniform asymptotic expansion for all the eigenvalues. Note however, that the considered symbol does not fully satisfy the conditions imposed in previous works, but only in a small neighborhood of the singularity point. In the present work: (i) We construct and justify the asymptotic formulas of the SL method for the eigenvalues λ j ( T n ( a ) ) $$ {\lambda}_j\left({T}_n(a)\right) $$ with j ε n $$ j\geqslant \varepsilon n $$ , where the eigenvalues are arranged in nondecreasing order and ε $$ \varepsilon $$ is a sufficiently small fixed number. (ii) We show, with the help of numerical calculations, that the obtained formulas give good approximations in the case j < ε n $$ j<\varepsilon n $$ . (iii) We numerically show that the main term of the asymptotics for eigenvalues with j < ε n $$ j<\varepsilon n $$ , formally obtained from the formulas of the SL method, coincides with the main term of the asymptotics constructed and justified in the classical works of Widom and Parter.  相似文献   

4.
A general, rectangular kernel matrix may be defined as K i j = κ ( x i , y j ) $$ {K}_{ij}=\kappa \left({x}_i,{y}_j\right) $$ where κ ( x , y ) $$ \kappa \left(x,y\right) $$ is a kernel function and where X = { x i } i = 1 m $$ X={\left\{{x}_i\right\}}_{i=1}^m $$ and Y = { y i } i = 1 n $$ Y={\left\{{y}_i\right\}}_{i=1}^n $$ are two sets of points. In this paper, we seek a low-rank approximation to a kernel matrix where the sets of points X $$ X $$ and Y $$ Y $$ are large and are arbitrarily distributed, such as away from each other, “intermingled”, identical, and so forth. Such rectangular kernel matrices may arise, for example, in Gaussian process regression where X $$ X $$ corresponds to the training data and Y $$ Y $$ corresponds to the test data. In this case, the points are often high-dimensional. Since the point sets are large, we must exploit the fact that the matrix arises from a kernel function, and avoid forming the matrix, and thus ruling out most algebraic techniques. In particular, we seek methods that can scale linearly or nearly linearly with respect to the size of data for a fixed approximation rank. The main idea in this paper is to geometrically select appropriate subsets of points to construct a low rank approximation. An analysis in this paper guides how this selection should be performed.  相似文献   

5.
In this paper, we propose and analyze the numerical algorithms for fast solution of periodic elliptic problems in random media in d $$ {\mathbb{R}}^d $$ , d = 2 , 3 $$ d=2,3 $$ . Both the two-dimensional (2D) and three-dimensional (3D) elliptic problems are considered for the jumping equation coefficients built as a checkerboard type configuration of bumps randomly distributed on a large L × L $$ L\times L $$ , or L × L × L $$ L\times L\times L $$ lattice, respectively. The finite element method discretization procedure on a 3D n × n × n $$ n\times n\times n $$ uniform tensor grid is described in detail, and the Kronecker tensor product approach is proposed for fast generation of the stiffness matrix. We introduce tensor techniques for the construction of the low Kronecker rank spectrally equivalent preconditioner in a periodic setting to be used in the framework of the preconditioned conjugate gradient iteration. The discrete 3D periodic Laplacian pseudo-inverse is first diagonalized in the Fourier basis, and then the diagonal matrix is reshaped into a fully populated third-order tensor of size n × n × n $$ n\times n\times n $$ . The latter is approximated by a low-rank canonical tensor by using the multigrid Tucker-to-canonical tensor transform. As an example, we apply the presented solver in numerical analysis of stochastic homogenization method where the 3D elliptic equation should be solved many hundred times, and where for every random sampling of the equation coefficient one has to construct the new stiffness matrix and the right-hand side. The computational characteristics of the presented solver in terms of a lattice parameter L $$ L $$ and the grid-size, n d $$ {n}^d $$ , in both 2D and 3D cases are illustrated in numerical tests. Our solver can be used in various applications where the elliptic problem should be solved for a number of different coefficients for example, in many-particle dynamics, protein docking problems or stochastic modeling.  相似文献   

6.
This paper describes and develops a fast and accurate path following algorithm that computes the field of values boundary curve F ( A ) $$ \partial F(A) $$ for every conceivable complex or real square matrix A $$ A $$ . It relies on the matrix flow decomposition algorithm that finds a proper block-diagonal flow representation for the associated hermitean matrix flow A ( t ) = cos ( t ) H + sin ( t ) K $$ {\mathcal{F}}_A(t)=\cos (t)H+\sin (t)K $$ under unitary similarity if that is possible. Here A ( t ) $$ {\mathcal{F}}_A(t) $$ is the 1-parameter-varying linear combination of the real and skew part matrices H = ( A + A ) / 2 $$ H=\left(A+{A}^{\ast}\right)/2 $$ and K = ( A A ) / ( 2 i ) $$ K=\left(A-{A}^{\ast}\right)/(2i) $$ of A $$ A $$ . For indecomposable matrix flows, A ( t ) $$ {\mathcal{F}}_A(t) $$ has just one block and the ZNN based field of values algorithm works with A ( t ) $$ {\mathcal{F}}_A(t) $$ directly. For decomposing flows A ( t ) $$ {\mathcal{F}}_A(t) $$ , the algorithm decomposes the given matrix A $$ A $$ unitarily into block-diagonal form U A U = diag ( A j ) $$ {U}^{\ast } AU=\operatorname{diag}\left({A}_j\right) $$ with j > 1 $$ j>1 $$ diagonal blocks A j $$ {A}_j $$ whose individual sizes add up to the size of A $$ A $$ . It then computes the field of values boundaries separately for each diagonal block A j $$ {A}_j $$ using the path following ZNN eigenvalue method. The convex hull of all sub-fields of values boundary points F ( A j ) $$ \partial F\left({A}_j\right) $$ finally determines the field of values boundary curve correctly for decomposing matrices A $$ A $$ . The algorithm removes standard restrictions for path following FoV methods that generally cannot deal with decomposing matrices A $$ A $$ due to possible eigencurve crossings of A ( t ) $$ {\mathcal{F}}_A(t) $$ . Tests and numerical comparisons are included. Our ZNN based method is coded for sequential and parallel computations and both versions run very accurately and fast when compared with Johnson's Francis QR eigenvalue and Bendixson rectangle based method and compute global eigenanalyses of A ( t k ) $$ {\mathcal{F}}_A\left({t}_k\right) $$ for large discrete sets of angles t k [ 0 , 2 π ] $$ {t}_k\in \left[0,2\pi \right] $$ more slowly.  相似文献   

7.
In the present article, we consider a class of elliptic partial differential equations with Dirichlet boundary conditions and where the operator is div(?a( x )?·), with a continuous and positive over Ω , Ω being an open and bounded subset of R d , d≥1. For the numerical approximation, we consider the classical P k Finite Elements, in the case of Friedrichs–Keller triangulations, leading, as usual, to sequences of matrices of increasing size. The new results concern the spectral analysis of the resulting matrix‐sequences in the direction of the global distribution in the Weyl sense, with a concise overview on localization, clustering, extremal eigenvalues, and asymptotic conditioning. We study in detail the case of constant coefficients on Ω=(0,1)2 and we give a brief account in the more involved case of variable coefficients and more general domains. Tools are drawn from the Toeplitz technology and from the rather new theory of Generalized Locally Toeplitz sequences. Numerical results are shown for a practical evidence of the theoretical findings.  相似文献   

8.
This article presents a multilevel parallel preconditioning technique for solving general large sparse linear systems of equations. Subdomain coloring is invoked to reorder the coefficient matrix by multicoloring the adjacency graph of the subdomains, resulting in a two‐level block diagonal structure. A full binary tree structure ?? is then built to facilitate the construction of the preconditioner. A key property that is exploited is the observation that the difference between the inverse of the original matrix and that of its block diagonal approximation is often well approximated by a low‐rank matrix. This property and the block diagonal structure of the reordered matrix lead to a multicolor low‐rank (MCLR) preconditioner. The construction procedure of the MCLR preconditioner follows a bottom‐up traversal of the tree ?? . All irregular matrix computations, such as ILU factorizations and related triangular solves, are restricted to leaf nodes where these operations can be performed independently. Computations in nonleaf nodes only involve easy‐to‐optimize dense matrix operations. In order to further reduce the number of iteration of the Preconditioned Krylov subspace procedure, we combine MCLR with a few classical block‐relaxation techniques. Numerical experiments on various test problems are proposed to illustrate the robustness and efficiency of the proposed approach for solving large sparse symmetric and nonsymmetric linear systems.  相似文献   

9.
In this work we consider the problem of semi‐active damping optimization of mechanical systems with fixed damper positions. Our goal is to compute a damping that is locally optimal with respect to the ? ‐norm of the transfer function from the exogenous inputs to the performance outputs. We make use of a new greedy method for computing the ? ‐norm of a transfer function based on rational interpolation. In this paper, this approach is adapted to parameter‐dependent transfer functions. The interpolation leads to parametric reduced‐order models that can be optimized more efficiently. At the optimizers we then take new interpolation points to refine the reduced‐order model and to obtain updated optimizers. In our numerical examples we show that this approach normally converges fast and thus can highly accelerate the optimization procedure. Another contribution of this work is heuristics for choosing initial interpolation points.  相似文献   

10.
We introduce the tensor numerical method for solving optimal control problems that are constrained by fractional two- (2D) and three-dimensional (3D) elliptic operators with variable coefficients. We solve the governing equation for the control function which includes a sum of the fractional operator and its inverse, both discretized over large 3D n × n × n spacial grids. Using the diagonalization of the arising matrix-valued functions in the eigenbasis of the one-dimensional Sturm–Liouville operators, we construct the rank-structured tensor approximation with controllable precision for the discretized fractional elliptic operators and the respective preconditioner. The right-hand side in the constraining equation (the optimal design function) is supposed to be represented in a form of a low-rank canonical tensor. Then the equation for the control function is solved in a tensor structured format by using preconditioned CG iteration with the adaptive rank truncation procedure that also ensures the accuracy of calculations, given an ε -threshold. This method reduces the numerical cost for solving the control problem to O ( n log n ) (plus the quadratic term O ( n 2 ) with a small weight), which outperforms traditional approaches with O ( n 3 log n ) complexity in the 3D case. The storage for the representation of all 3D nonlocal operators and functions involved is also estimated by O ( n log n ) . This essentially outperforms the traditional methods operating with fully populated n 3 × n 3 matrices and vectors in ? n 3 . Numerical tests for 2D/3D control problems indicate the almost linear complexity scaling of the rank truncated preconditioned conjugate gradient iteration in the univariate grid size n.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号