检索结果-内蒙古大学图书馆

ALGORITHM-AGNOSTIC LOW-RANK APPROXIMATION OF OPERATOR MONOTONE matrix functions

SIAM JOURNAL ON matrix ANALYSIS AND APPLICATIONS 2025年第1期46卷 1-21页

作者： Persson, David Meyer, Raphael a. Musco, Christopher EPF Lausanne Inst Math Lausanne Switzerland NYU New York NY 10012 USA

Low-rank approximation of a matrix function, f (A), is an important task in computational mathematics. Most methods require direct access to f (A), which is often considerably more expensive than accessing A. Persson and Kressner [SIAM J. matrix Anal., 44 (2023), pp. 415--944] avoid this issue for symmetric positive semidefinite matrices by proposing funNystro"\m, which first constructs a Nystro"\m approximation to A using subspace iteration and then uses the approximation to directly obtain a low-rank approximation for f (A). They prove that the method yields a near- optimal approximation whenever f is a continuous operator monotone function with f (0) = 0. We significantly generalize the results of Persson and Kressner beyond subspace iteration. We show that if Aat\wideh is a near-optimal low-rank Nystro"\m approximation to A, then f (At\wideha) is a near-optimal low-rank approximation to f (A), independently of how Aat\wideh is computed. Further, we show sufficient conditions for a basis Q to produce a near-optimal Nystro"\m approximation these results to establish that many common low-rank approximation methods produce near-optimal Nystro"\m approximations to A and therefore to f (A). Aat\wideh = AQ(QT AQ)tQT A. We use

关键词： low-rank approximation matrix functions numerical analysis

来源：评论

学校读者我要写书评

暂无评论

A message-passing approach to obtain the trace of matrix functions with applications to network analysis

引用

NUMERICAL ALGORITHMS 2025年 1-22页

作者： Guzman, Grover Enrique Castro Stadler, Peter Florian Fujita, Andre Univ Sao Paulo Inst Math & Stat Dept Comp Sci Rua Matao 1010 BR-05508090 Sao Paulo SP Brazil Univ Leipzig Dept Comp Sci Bioinformat Grp Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig German Ctr Integrat Biodivers Res iDiv Halle Jena Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Competence Ctr Scalable Data Serv & Solut Dresden Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Konrad Zuse Sch Excellence Embedded Composite AI D Hartelstr 16-18 D-04107 Leipzig Germany Max Planck Inst Math Sci Inselstr 22 D-04103 Leipzig Germany Univ Vienna Inst Theoret Chem Waehringerstr 17 A-1090 Vienna Austria Univ Nacl Colombia Fac Ciencias Sede Bogota Bogota Colombia Santa Fe Inst 1399 Hyde Pk Rd Santa Fe NM 87501 USA Kyushu Univ Med Inst Bioregulat Div Network AI Stat Fukuoka Japan

Graphs have become a commonly used model to study technological, biological, and social systems. Various methods have been proposed to measure graphs' structural and dynamical properties, providing insights into the fundamental processes and interactions that govern the behavior of these systems. matrix functions are powerful mathematical tools for assessing vertex centrality, communicability, and diffusion processes. Let M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{M}$$\end{document} be the adjacency matrix of a weighted undirected graph. Then, the trace of matrix functions, tr(f(M))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varvec{{{\,\textrm{tr}\,}}}(\varvec{f}(\textbf{M}))$$\end{document}, provides insights into global network structural and dynamical properties. Although tr(f(M))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varvec{{{\,\textrm{tr}\,}}}(\varvec{f}(\textbf{M}))$$\end{document} can be computed using the diagonalization method for graphs with a few thousand vertices, this approach is impractical for large-scale networks due to its computational complexity. Here, we present a message-passing method to approximate tr(f(M))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varvec{{{\,\textrm{tr}\,}}}(\varvec{f}(\textbf{

关键词： Message-passing matrix functions Cauchy integrals Lanczos Chebyshev

来源：评论

学校读者我要写书评

暂无评论

New block quadrature rules for the approximation of matrix functions

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2016年 502卷 299-326页

作者： Reichel, Lothar Rodriguez, Giuseppe Tang, Tunan Kent State Univ Dept Math Sci Kent OH 44242 USA Univ Cagliari Dipartimento Matemat & Informat Viale Merello 92 I-09123 Cagliari Italy

Golub and Meurant have shown how to use the symmetric block Lanczos algorithm to compute block Gauss quadrature rules for the approximation of certain matrix functions. We describe new block quadrature rules that can be computed by the symmetric or nonsymmetric block Lanczos algorithms and yield higher accuracy than standard block Gauss rules after the same number of steps of the symmetric or nonsymmetric block Lanczos algorithms. The new rules are block generalizations of the generalized averaged Gauss rules introduced by Spalevic. Applications to network analysis are presented. (C) 2015 Elsevier Inc. All rights reserved.

关键词： matrix functions Gauss quadrature Block Lanczos algorithm Complex networks

来源：评论

学校读者我要写书评

暂无评论

A Fast Monte Carlo Algorithm for Evaluating matrix functions with Application in Complex Networks

引用

JOURNAL OF SCIENTIFIC COMPUTING 2024年第2期99卷 41-41页

作者： Guidotti, Nicolas L. Acebron, Juan A. Monteiro, Jose Univ Lisbon Inst Super Tecn INESC ID Lisbon Portugal Carlos III Univ Madrid Dept Math Leganes Spain

We propose a novel stochastic algorithm that randomly samples entire rows and columns of the matrix as a way to approximate an arbitrary matrix function using the power series expansion. This contrasts with existing Monte Carlo methods, which only work with one entry at a time, resulting in a significantly better convergence rate than the original approach. To assess the applicability of our method, we compute the subgraph centrality and total communicability of several large networks. In all benchmarks analyzed so far, the performance of our method was significantly superior to the competition, being able to scale up to 64 CPU cores with remarkable efficiency.

关键词： Monte Carlo methods Randomized algorithms matrix functions Network analysis

来源：评论

学校读者我要写书评

暂无评论

A nonlocal constitutive model generated by matrix functions for polyatomic periodic linear chains

引用

ARCHIVE OF APPLIED MECHANICS 2014年第9-11期84卷 1477-1500页

作者： Michelitsch, Thomas Collet, Bernard Univ Paris 06 Inst Jean le Rond dAlembert Sorbonne Univ CNRSUMR 7190 F-75252 Paris 05 France

We establish a discrete lattice dynamics model and its continuum limits for nonlocal constitutive behavior of polyatomic cyclically closed linear chains being formed by periodically repeated unit cells (molecules), each consisting of atoms which all are of different species, e.g., distinguished by their masses. Nonlocality is introduced by elastic potentials which are quadratic forms of finite differences of orders of the displacement field leading by application of Hamilton's variational principle to nondiagonal and hence nonlocal Laplacian matrices. These Laplacian matrices are obtained as matrix power functions of even orders 2m of the local discrete Laplacian of the next neighbor Born-von-Karman linear chain. The present paper is a generalization of a recent model that we proposed for the monoatomic chain. We analyze the vibrational dispersion relation and continuum limits of our nonlocal approach. "Anomalous" dispersion relation characteristics due to strong nonlocality which cannot be captured by classical lattice models is found and discussed. The requirement of finiteness of the elastic energies and total masses in the continuum limits requires a certain scaling behavior of the material constants. In this way, we deduce rigorously the continuum limit kernels of the Laplacian matrices of our nonlocal lattice model. The approach guarantees that these kernels correspond to physically admissible, elastically stable chains. The present approach has the potential to be extended to 2D and 3D lattices.

关键词： Linear polyatomic chains matrix functions Nonlocal constitutive laws Elastic convolution kernels Long-wave continuum limit Acoustic and optic branches

来源：评论

学校读者我要写书评

暂无评论

Fractional Fourier, Hartley, Cosine and Sine Number-Theoretic Transforms Based on matrix functions

引用

CIRCUITS SYSTEMS AND SIGNAL PROCESSING 2017年第7期36卷 2893-2916页

作者： Lima, Paulo Hugo E. S. Lima, Juliano B. Campello de Souza, Ricardo M. Univ Fed Pernambuco Dept Elect & Syst Recife PE Brazil

In this paper, we introduce fractional number-theoretic transforms (FrNTT) based on matrix functions. In contrast to previously proposed FrNTT, our approach does not require the construction of any number-theoretic transform (NTT) eigenvectors set. This allows us to obtain an FrNTT matrix by means of a closed-form expression corresponding to a linear combination of integer powers of the respective NTT matrix. Fractional Fourier, Hartley, cosine and sine number-theoretic transforms are developed. We show that fast algorithms applicable to ordinary NTT can also be used to compute the proposed FrNTT. Furthermore, we investigate the relationship between fractional Fourier and Hartley number-theoretic transforms, and demonstrate the applicability of the proposed FrNTT to a recently introduced image encryption scheme.

关键词： Number-theoretic transforms Fractional transforms matrix functions Image encryption

来源：评论

学校读者我要写书评

暂无评论

Evaluation of matrix functions with the block Lanczos algorithm

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 1997年第1-2期33卷 45-57页

作者： Cabos, C Germanischer Lloyd P.O.B. 111606 D-20416 Hamburg Germany

For the approximate eigenvalues and eigenvectors obtained from a block Lanczos iteration, characterizations are given in terms of vectors of polynomials. It is proven that after r steps of block Lanczos with selfadjoint iteration matrix S, the application p(S)f of a matrix polynomial and the linear functional (v, q(S)f) can be evaluated exactly, if p and q are polynomials of degree r - 1 and 2r - 1, respectively. For that, the Lanczos starting block should contain the vectors f and v. Based on this property a priori error bounds for the evaluation of g(S)f and (v, g(S)f) for more general functions g are derived. The error bounds are applied to the case of calculating the dynamic response in forced vibration problems. A numerical example is given.

关键词： block Lanczos method Ritz vectors matrix functions forced vibrations error bounds

来源：评论

学校读者我要写书评

暂无评论

THE RADAU-LANCZOS METHOD FOR matrix functions

引用

SIAM JOURNAL ON matrix ANALYSIS AND APPLICATIONS 2017年第3期38卷 710-732页

作者： Frommer, Andreas Lund, Kathryn Schweitzer, Marcel Szyld, Daniel B. Berg Univ Wuppertal Fak Math & Nat Wissensch D-42097 Wuppertal Germany Temple Univ 038 16 Dept Math Philadelphia PA 19122 USA

Analysis and development of restarted Krylov subspace methods for computing f (A) b have proliferated in recent years. We present an acceleration technique for such methods when applied to Stieltjes functions f and Hermitian positive definite matrices A. This technique is based on a rank-one modification of the Lanczos matrix derived from a connection between the Lanczos process and Gauss-Radau quadrature. We henceforth refer to the technique paired with the standard Lanczos method for matrix functions as the Radau-Lanczos method for matrix functions. We develop properties of general rank-one updates, leading to a framework through which other such updates could be explored in the future. We also prove error bounds for the Radau-Lanczos method, which are used to prove the convergence of restarted versions. We further present a thorough investigation of the Radau-Lanczos method explaining why it routinely improves over the standard Lanczos method. This is confirmed by several numerical experiments, and we conclude that, in practical situations, the Radau-Lanczos method is superior in terms of iteration counts and timings, when compared to the standard Lanczos method.

关键词： matrix functions Krylov subspace methods restarted Lanczos method Gaussian quadrature Gauss-Radau quadrature

来源：评论

学校读者我要写书评

暂无评论

Computation of matrix functions with deflated restarting

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2013年第1期237卷 223-233页

作者： Gu, Chuanqing Zheng, Lin Shanghai Univ Dept Math Shanghai 200444 Peoples R China

A deflated restarting Krylov subspace method for approximating a function of a matrix times a vector is proposed. In contrast to other Krylov subspace methods, the performance of the method in this paper is better. We further show that the deflating algorithm inherits the superlinear convergence property of its unrestarted counterpart for the entire function and present the results of numerical experiments. (C) 2012 Elsevier B.V. All rights reserved.

关键词： matrix functions Krylov subspace approximation Restarted Arnoldi method Deflated restarting Krylov subspace method

来源：评论

学校读者我要写书评

暂无评论

QUANTUM ALGORITHM FOR matrix functions BY CAUCHY'S INTEGRAL FORMULA

引用

QUANTUM INFORMATION & COMPUTATION 2020年第1-2期20卷 14-36页

作者： Takahira, Souichi Ohashi, Asuka Sogabe, Tomohiro Usuda, Tsuyoshi Sasaki Aichi Prefectural Univ Grad Sch Informat Sci & Technol 1522-3 Ibaragabasama Nagakute Aichi 4801198 Japan Ritsumeikan Univ Coll Sci & Engn 1-1-1 Noji Higashi Kusatsu Shiga 5258577 Japan Nagoya Univ Grad Sch Engn Chikusa Ku Furo Cho Nagoya Aichi 4648603 Japan

For matrix A, vector b and function f, the computation of vector f (A)b arises in many scientific computing applications. We consider the problem of obtaining quantum state vertical bar f > corresponding to vector f (A)b. There is a quantum algorithm to compute state vertical bar f > using eigenvalue estimation that uses phase estimation and Hamiltonian simulation e(iAt). However, the algorithm based on eigenvalue estimation needs poly(1/epsilon) runtime, where epsilon is the desired accuracy of the output state. Moreover, if matrix A is not Hermitian, e(iAt) is not unitary and we cannot run eigenvalue estimation. In this paper, we propose a quantum algorithm that uses Cauchy's integral formula and the trapezoidal rule as an approach that avoids eigenvalue estimation. We show that the runtime of the algorithm is poly(log(1/epsilon) and the algorithm outputs state vertical bar f > even if A is not Hermitian.

关键词： Quantum algorithm matrix functions HHL algorithm Cauchy's integral formula

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：