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

JOURNAL OF SYMBOLIC COMPUTATION 2013年 50卷 208-226页

作者： Roy, Marie-Francoise Sedjelmaci, Sidi Mohamed Univ Rennes IRMAR URA 305 CNRS F-35042 Rennes France Univ Paris 13 LIPN UMR 7030 CNRS F-93430 Villetaneuse France

We give new simple algorithms for the fast computation of the quotient boot and the gcd of two polynomials, and obtain a complexity 0 (d(log(2)d)(2)), where d is the degree of the polynomials, similarly to Schonhage (1971), Moenck (1973). More precisely, denoting by M(d) the cost of a fast multiplication of polynomials of degree d, we reach the complexity (9/2M(d) + 0(d))log2d where d is the degree of the polynomials in the non-defective case (when degrees drop one by one), and (21M(d) + 0(d))log2d + 0(M(d)) in the general case, improving the complexity bounds (respectively (10M(d) + 0(d)) log(2) d and (24M(d) + 0(d))log2d + 0(M(d))) previously known for these problems (von zur Gathen and Gerhard, 1999, see Exercise 11.7). We hope that the simple character of our algorithms will make it easier to use fast algorithms in practice for these problems. (C) 2012 Elsevier B.V. All rights reserved.

关键词： fast algorithms Greatest common divisor (gcd) Half-greatest common divisor (half-gcd) Quotient boot Complexity

来源：评论

学校读者我要写书评

暂无评论

The FFTRR-based fast direct algorithms for complex inhomogeneous biharmonic problems with applications to incompressible flows

引用

NUMERICAL algorithms 2017年第4期75卷 937-971页

作者： Daripa, Prabir Ghosh, Aditi Texas A&M Univ Dept Math College Stn TX 77843 USA

We develop analysis-based fast and accurate direct algorithms for several biharmonic problems in a unit disk derived directly from the Green's functions of these problems and compare the numerical results with the "decomposition" algorithms (see Ghosh and Daripa, IMA J. Numer. Anal. 36(2), 824-850 [17]) in which the biharmonic problems are first decomposed into lower order problems, most often either into two Poisson problems or into two Poisson problems and a homogeneous biharmonic problem. One of the steps in the "decomposition algorithm" as discussed in Ghosh and Daripa (IMA J. Numer. Anal. 36(2), 824-850 [17]) for solving certain biharmonic problems uses the "direct algorithm" without which the problem can not be solved. Using classical Green's function approach for these biharmonic problems, solutions of these problems are represented in terms of singular integrals in the complex z-plane (the physical plane) involving explicitly the boundary conditions. Analysis of these singular integrals using FFT and recursive relations (RR) in Fourier space leads to the development of these fast algorithms which are called FFTRR based algorithms. These algorithms do not need to do anything special to overcome coordinate singularity at the origin as often the case when solving these problems using finite difference methods in polar coordinates. These algorithms have some other desirable properties such as the ease of implementation and parallel in nature by construction. Moreover, these algorithms have O(logN) complexity per grid point where N (2) is the total number of grid points and have very low constant behind this order estimate of the complexity. Performance of these algorithms is shown on several test problems. These algorithms are applied to solving viscous flow problems at low and moderate Reynolds numbers and numerical results are presented.

关键词： Complex Biharmonic equation Green's function fast algorithms Stokes equations Steady incompressible flows FFT Recursive relations Numerical implementation in Matlab

来源：评论

学校读者我要写书评

暂无评论

fast and stable algorithms for banded plus semiseparable systems of linear equations

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2003年第2期25卷 373-384页

作者： Chandrasekaran, S Gu, M Univ Calif Santa Barbara Dept Elect & Comp Engn Santa Barbara CA 93106 USA Univ Calif Berkeley Dept Math Berkeley CA 94720 USA

We present fast and numerically stable algorithms for the solution of linear systems of equations, where the coefficient matrix can be written in the form of a banded plus semiseparable matrix. Such matrices include banded matrices, banded bordered matrices, semiseparable matrices, and block-diagonal plus semiseparable matrices as special cases. Our algorithms are based on novel matrix factorizations developed specifically for matrices with such structures. We also present interesting numerical results with these algorithms.

关键词： banded matrix bordered matrix semiseparable matrix H-matrix fast algorithms stable algorithms

来源：评论

学校读者我要写书评

暂无评论

fast and accurate algorithms for quadratic phase integrals in optics and signal processing

Fast and accurate algorithms for quadratic phase integrals i...

引用

Conference on Three-Dimensional Imaging, Visualization, and Display 2011

作者： Koc, Aykut Ozaktas, Haldun M. Hesselink, Lambertus Stanford Univ Dept Elect Engn Stanford CA 94305 USA Bilkent Univ Elect Engn Dept Bilkent Turkey

ISBN: (纸本)9780819486172

The class of two-dimensional non-separable linear canonical transforms is the most general family of linear canonical transforms, which are important in both signal/image processing and optics. Application areas include noise filtering, image encryption, design and analysis of ABCD systems, etc. To facilitate these applications, one need to obtain a digital computation method and a fast algorithm to calculate the input-output relationships of these transforms. We derive an algorithm of NlogN time, N being the space-bandwidth product. The algorithm controls the space-bandwidth products, to achieve information theoretically sufficient, but not redundant, sampling required for the reconstruction of the underlying continuous functions.

关键词： Linear Canonical Transforms Quadratic-Phase Systems ABCD optics transforms fast algorithms

来源：评论

学校读者我要写书评

暂无评论

fast quantum algorithms for quantum soft computing and simulation of robust intelligent control systems

Fast quantum algorithms for quantum soft computing and simul...

引用

5th International Symposium on Soft Computing for Industry held at the 6th Biannual World Automation Congress

作者： Panfilov, S Takahashi, K Ulyanov, I Yamaha-Motor Europe N.V. R and D Office Italy TSK Expotech Ltd. Russian Federation

ISBN: (纸本)1889335231

The general approach for quantum algorithm simulation in Quantum Soft Computing on classical computer is introduced. Efficient fast algorithm for simulation of Grover's quantum search algorithm (QSA) in unsorted database is presented. Comparison with common quantum algorithm simulation approach is demonstrated. Application in the design process of robust knowledge bases for fuzzy control is described.

关键词： quantum algorithm efficient simulation fast algorithms

来源：评论

学校读者我要写书评

暂无评论

Equispaced Fourier Representations for Efficient Gaussian Process Regression from a Billion Data Points

引用

SIAM-ASA JOURNAL ON UNCERTAINTY QUANTIFICATION 2025年第1期13卷 63-89页

作者： Greengard, Philip Rachh, Manas Barnett, Alex H. Columbia Univ Dept Stat New York NY 10027 USA Flatiron Inst Ctr Computat Math New York NY 10010 USA

We introduce a Fourier-based fast algorithm for Gaussian process regression in low dimensions. It approximates a translationally-invariant covariance kernel by complex exponentials on an equispaced Cartesian frequency grid of M nodes. This results in a weight-space MxM system matrix with Toeplitz structure, which can thus be applied to a vector in O(M log M) operations via the fast Fourier transform (FFT), independent of the number of data points N. The linear system can be set up in O(N+M log M) operations using nonuniform FFTs. This enables efficient massive-scale regression via an iterative solver, even for kernels with fat-tailed spectral densities (large M). We provide bounds on both kernel approximation and posterior mean errors. Numerical experiments for squared-exponential and Mat & eacute;rn kernels in one, two and three dimensions often show 1-2 orders of magnitude acceleration over state-of-the-art rank-structured solvers at comparable accuracy. Our method allows 2D Mat & eacute;rn-32 regression from N=10(9) data points to be performed in 2 minutes on a standard desktop, with posterior mean accuracy 10(-3). This opens up spatial statistics applications 100 times larger than previously possible.

关键词： Gaussian process regression fast algorithms nonuniform FFT Fourier basis covariance kernel

来源：评论

学校读者我要写书评

暂无评论

Multichannel fast QRD-RLS adaptive filtering: Block-channel and sequential-channel algorithms based on updating backward prediction errors

引用

SIGNAL PROCESSING 2007年第7期87卷 1781-1798页

作者： Ramos, A. L. L. Apolinario, J. A., Jr. Werner, S. Inst Militar Engn Dept Elect Engn BR-22290270 Rio De Janeiro Brazil Helsinki Univ Technol Signal Proc Lab FIN-02015 Helsinki Finland

fast QR decomposition recursive least-squares (FQRD-RLS) algorithms are well known for their fast convergence and reduced computational complexity. A considerable research effort has been devoted to the investigation of single-channel versions of the FQRD-RLS algorithms, while the multichannel counterparts have not received the same attention. The goal of this paper is to broaden the study of the efficient and low complexity family of multichannel RLS adaptive filters, and to offer new algorithm options. We present a generalized approach for block-type multichannel FQRD-RLS (MG FQRD-RLS) algorithms that includes both cases of equal and multiple order. We also introduce new versions for block-channel and sequential -channel processing, details of their derivations, and a comparison in terms of computational complexity. The proposed algorithms are based on the updating of backward a priori and a posteriori error vectors, which are known to be numerically robust. (c) 2007 Elsevier B.V. All rights reserved.

关键词： adaptive systems fast algorithms QR decomposition multichannel algorithms order recursive algorithms

来源：评论

学校读者我要写书评

暂无评论

fast asynchronous updating algorithms for k-shell indices

引用

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS 2017年 482卷 524-531页

作者： Lee, Yan-Li Zhou, Tao Univ Elect Sci & Technol China CompleX Lab Web Sci Ctr Chengdu 611731 Sichuan Peoples R China Univ Elect Sci & Technol China Big Data Res Ctr Chengdu 611731 Sichuan Peoples R China

Identifying influential nodes in networks is a significant and challenging task. Among many centrality indices, the k-shell index performs very well in finding out influential spreaders. However, the traditional method for calculating the k-shell indices of nodes needs the global topological information, which limits its applications in large-scale dynamically growing networks. Recently, Lu et al. [Nature Commun. 7 (2016) 10168] proposed a novel asynchronous algorithm to calculate the k-shell indices, which is suitable to deal with large-scale growing networks. In this paper, we propose two algorithms to select nodes and update their intermediate values towards the k-shell indices, which can help in accelerating the convergence of the calculation of k-shell indices. The former algorithm takes into account the degrees of nodes while the latter algorithm prefers to choose the node whose neighbors' values have been changed recently. We test these two methods on four real networks and four artificial networks. The results suggest that the two algorithms can respectively reduce the convergence time up to 75.4% and 92.9% in average, compared with the original asynchronous updating algorithm. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Complex networks Vital nodes identification k-shell index fast algorithms

来源：评论

学校读者我要写书评

暂无评论

algorithms for unequally spaced fast Laplace transforms

引用

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS 2013年第3期35卷 419-432页

作者： Andersson, Fredrik Lund Univ Ctr Math Sci SE-22100 Lund Sweden

fast algorithms for unequally spaced discrete Laplace transforms are presented. The algorithms are approximate up to a prescribed choice of computational precision, and they employ modified versions of algorithms for unequally spaced fast Fourier transforms using Gaussians. Various configurations of sums with equally and unequally spaced points can be dealt with. In contrast to previously presented fast algorithms for fast discrete Laplace transforms, the proposed algorithms are not restricted to the case of real exponentials but can deal with oscillations caused by complex valued nodes. Numerical experiments show that the computational complexity is comparable to that of computing ordinary discrete Fourier transforms by means of FFT. Results are given for the one-dimensional case, but it is straightforward to generalize them to arbitrary dimensions. (C) 2012 Elsevier Inc. All rights reserved.

关键词： Discrete Laplace transforms fast algorithms USFFT fast application of complex Vandermonde matrices

来源：评论

学校读者我要写书评

暂无评论

fast square-root RLS adaptive filtering algorithms

引用

SIGNAL PROCESSING 1997年第3期57卷 233-250页

作者： Carini, A Mumolo, E UNIV TRIESTE DIPARTIMENTO ELETTROTECN ELETTRON INFORMAT I-34127 TRIESTE ITALY

In this paper two fast RLS adaptive filtering algorithms are described. Both algorithms compute the lattice coefficients and are based on the development of square-root factorizations of the autocorrelation matrix. Due to the square-root nature of the algorithms, the recursion is numerically stable. Experimental evaluations have been performed in limited precision environment, and comparison with the stabilized fast transversal filter algorithm (Slock and Kailath, 1991) has been made. Since the described algorithms require O(N) operations per sample, where N is the filter order, from a computational complexity point of view they represent a substantial advantage over the O(N-2) complexity of classical square-root algorithms. (C) 1997 Elsevier Science B.V.

关键词： adaptive filtering fast algorithms recursive least squares square-root factorization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：