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

A CLASS OF RANDOM NUMBER GENERATORS BASED ON WEYL SEQUENCE

Applied Mathematics(A Journal of Chinese Universities) 2005年第4期20卷 483-490页

作者： Liang Heng Liu Qinghua Bai Fengshan Dept. of Math. Sci. Tsinghua Univ. Beijing 100084China.

The generation of good pseudo-random numbers is the base of many important fields in scientific computing, such as randomized algorithms and numerical solution of stochastic differential equations. In this paper, a class of random number generators （RNGs） based on Weyl sequence is proposed. The uniformity of those RNGs is proved theoretically. Statistical and numerical computations show the efficiency of the methods.

关键词： pseudo-random number randomized algorithm statistical test uniform distribution.

来源：评论

学校读者我要写书评

暂无评论

Reduction of Phase Shifters in Planar Phased Arrays Using Novel Random Subarray Techniques

引用

APPLIED SCIENCES-BASEL 2024年第13期14卷

作者： Valle, Juan L. Panduro, Marco A. Bocio, Carlos del Rio Brizuela, Carlos A. Covarrubias, David H. Ctr Sci Res & Higher Educ Ensenada CICESE Carr Tijuana Ensenada 3918 Ensenada 22860 Mexico Publ Univ Navarre UPNA Elect Elect & Commun Engn Pamplona 31006 Spain

Reducing the number of phase shifters by grouping antenna elements into subarrays has been extensively studied for decades. The number of phase shifters directly affects the cost, complexity, and power consumption of the system. A novel method for the design of phased planar antenna arrays is presented in this work in order to perform a reduction of up to 70% in the number of phase shifters used by the array, while maintaining the desired radiation characteristics. This method consists of creating fusions of subarrays to generate random sequences that form the best feeding network configuration for planar phased arrays. The obtained solution allows scanning the mainlobe at theta=-40(degrees) elevation with a range of scanning of [-75(degrees)

关键词： beamforming planar array phase shifter randomized algorithm subarray

来源：评论

学校读者我要写书评

暂无评论

INTERPOLATIVE BUTTERFLY FACTORIZATION

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2017年第2期39卷 A503-A531页

作者： Li, Yingzhou Yang, Haizhao Stanford Univ ICME Stanford CA 94305 USA Duke Univ Dept Math Durham NC 27708 USA

This paper introduces the interpolative butterfly factorization for nearly optimal implementation of several transforms in harmonic analysis, when their explicit formulas satisfy certain analytic properties and the matrix representations of these transforms satisfy a complementary low-rank property. A preliminary interpolative butterfly factorization is constructed based on interpolative low-rank approximations of the complementary low-rank matrix. A novel sweeping matrix compression technique further compresses the preliminary interpolative butterfly factorization via a sequence of structure-preserving low-rank approximations. The sweeping procedure propagates the low-rank property among neighboring matrix factors to compress dense submatrices in the preliminary butterfly factorization to obtain an optimal one in the butterfly scheme. For an N x N matrix, it takes O(N log N) operations and complexity to construct the factorization as a product of O(log N) sparse matrices, each with O(N) nonzero entries. Hence, it can be applied rapidly in O(N log N) operations. Numerical results are provided to demonstrate the effectiveness of this algorithm.

关键词： data-sparse matrix butterfly algorithm randomized algorithm matrix factorization operator compression nonuniform Fourier transform Fourier integral operators

来源：评论

学校读者我要写书评

暂无评论

Exact simulation of diffusion first exit times: algorithm acceleration

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2022年第1期23卷 6185-6204页

作者： Samuel Herrmann Cristina Zucca Institut de Mathématiques de Bourgogne (IMB) UMR 5584 CNRS Université de Bourgogne Franche-Comté Dijon France Department of Mathematics 'G. Peano' University of Torino Turin Italy

In order to describe or estimate different quantities related to a specific random variable, it is of prime interest to numerically generate such a variate. In specific situations, the exact generation of random variables might be either momentarily unavailable or too expensive in terms of computation time. It therefore needs to be replaced by an approximation procedure. As was previously the case, the ambitious exact simulation of first exit times for diffusion processes was unreachable though it concerns many applications in different fields like mathematical finance, neuroscience or reliability. The usual way to describe first exit times was to use discretization schemes, that are of course approximation procedures. Recently, Herrmann and Zucca (Herrmann and Zucca, 2020) proposed a new algorithm, the so-called GDET-algorithm (General Diffusion Exit Time), which permits to simulate exactly the first exit time for one-dimensional diffusions. The only drawback of exact simulation methods using an acceptance-rejection sampling is their time consumption. In this paper the authors highlight an acceleration procedure for the GDET-algorithm based on a multi-armed bandit model. The efficiency of this acceleration is pointed out through numerical examples.

关键词： exit time Brownian motion diffusion processes rejection sampling exact simulation multi-armed bandit randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximate Nearest Neighbor Search for a Dataset of Normalized Vectors

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2009年第9期E92D卷 1609-1619页

作者： Terasawa, Kengo Tanaka, Yuzuru Future Univ Hakodate Hakodate Hokkaido 3320012 Japan Japan Sci & Technol Agcy PRESTO Kawaguchi Saitama 3320012 Japan Hokkaido Univ Meme Media Lab Sapporo Hokkaido 0608628 Japan

This paper describes a novel algorithm for approximate nearest neighbor searching. For solving this problem especially in high dimensional spaces, one of the best-known algorithm is Locality-Sensitive Hashing (LSH). This paper presents a variant of the LSH algorithm that outperforms previously proposed methods when the dataset consists of vectors normalized to unit length, which is often the case in pattern recognition. The LSH scheme is based on a family of hash functions that preserves the locality of points. This paper points out that for our special case problem we can design efficient hash functions that map a point on the hypersphere into the closest vertex of the randomly rotated regular polytope. The computational analysis confirmed that the proposed method could improve the exponent p, the main indicator of the performance of the LSH algorithm. The practical experiments also supported the efficiency of our algorithm both in time and in space.

关键词： nearest neighbor randomized algorithm locality-sensitive hashing (LSH)

来源：评论

学校读者我要写书评

暂无评论

MULTIWAY MONTE CARLO METHOD FOR LINEAR SYSTEMS

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2019年第6期41卷 A3449-A3475页

作者： Wu, Tao Gleich, David F. Purdue Univ Dept Comp Sci W Lafayette IN 47906 USA

We study a novel variation on the Ulam-von Neumann Monte Carlo method for solving a linear system. This is an old randomized procedure that results from using a random walk to stochastically evaluate terms in the Neumann series. In order to apply this procedure, the variance of the stochastic estimator needs to be bounded. The best known sufficient condition for bounding the variance is that the infinity norm of the matrix in the Neumann series is smaller than one, which greatly limits the usability of this method. We improve this condition by proposing a new stochastic estimator based on a different type of random walk. Our multiway walk and estimator is based on a time-inhomogeneous Markov process that iterates through a sequence of transition matrices built from the original linear system. For our new method, we prove that a necessary and sufficient condition for convergence is that the spectral radius of the elementwise absolute value of the matrix underlying the Neumann series is smaller than one. This is a strictly weaker condition than currently exists. In addition, our new method is often faster than the standard algorithm. Through experiments, we demonstrate the potential for our method to reduce the time needed to solve linear equations by incorporating it into an outer iterative method.

关键词： Markov chain Monte Carlo linear solver randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

XTRACE: MAKING THE MOST OF EVERY SAMPLE IN STOCHASTIC TRACE ESTIMATION

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2024年第1期45卷 1-23页

作者： Epperly, Ethan N. Tropp, Joel A. Webber, Robert J. CALTECH Div Comp & Math Sci Pasadena CA 91125 USA

The implicit trace estimation problem asks for an approximation of the trace of a square matrix, accessed via matrix-vector products (matvecs). This paper designs new randomized algorithms, XTRACE and XNYsTRACE, for the trace estimation problem by exploiting both variance reduction and the exchangeability principle. For a fixed budget of matvecs, numerical experiments show that the new methods can achieve errors that are orders of magnitude smaller than existing algorithms, such as the Girard-Hutchinson estimator or the Hutch++ estimator. A theoretical analysis confirms the benefits by offering a precise description of the performance of these algorithms as a function of the spectrum of the input matrix. The paper also develops an exchangeable estimator, XDiag, for approximating the diagonal of a square matrix using matvecs.

关键词： trace estimation low-rank approximation exchangeability variance reduction randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Jacobian sparsity detection using Bloom filters

引用

OPTIMIZATION METHODS & SOFTWARE 2024年

作者： Hovland, Paul D. Argonne Natl Lab Res Partnerships 9700 S Cass Ave Lemont IL 60439 USA

Determining Jacobian sparsity structure is an important step in the efficient computation of sparse Jacobians. We introduce a new method for determining Jacobian sparsity patterns by combining bit vector probing with Bloom filters. We further refine Bloom filter probing by combining it with hierarchical probing to yield a highly effective strategy for Jacobian sparsity pattern determination.

关键词： Sparsity automatic differentiation Bloom filter randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

RAPID APPLICATION OF THE SPHERICAL HARMONIC TRANSFORM VIA INTERPOLATIVE DECOMPOSITION BUTTERFLY FACTORIZATION

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2021年第6期43卷 A3789-A3808页

作者： Bremer, James Chen, Ze Yang, Haizhao Univ Calif Davis Dept Math Davis CA 95616 USA Natl Univ Singapore Dept Math Select Reg Singapore 11907 Singapore Purdue Univ Dept Math W Lafayette IN 47907 USA

We describe an algorithm for the application of the forward and inverse spherical harmonic transforms. It is based on a new method for rapidly computing the forward and inverse associated Legendre transforms by hierarchically applying the interpolative decomposition butterfly factorization. Experimental evidence suggests that the complexity of our method-including all necessary precomputations-is O(N-2 log(3) N) in terms of both flops and memory, where N is the order of the transform. This is nearly asymptotically optimal. Moreover, unlike existing algorithms which are asymptotically optimal or nearly so, the constants in the running time and memory costs of our algorithm are small enough to make it competitive with state-of-the-art O(N-3) methods at relatively small values of N (e.g., N = 1024). Numerical results are provided to demonstrate the effectiveness and numerical stability of the new framework.

关键词： spherical harmonic transform Legendre transform block partitioning butterfly factorization interpolative decomposition randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Adaptive surrogate model coupled with stochastic configuration network strategies for time-dependent reliability assessment

引用

PROBABILISTIC ENGINEERING MECHANICS 2023年 71卷

作者： Liu, Huizhen Li, Shangjie Huang, Xianzhen Northeastern Univ Sch Mech Engn & Automation Shenyang 110819 Peoples R China Northeastern Univ Key Lab Vibrat & Control Aeroprop Syst Minist Educ China Shenyang 110819 Peoples R China

Time-dependent reliability assessment is crucial in enhancing product development economics and product performance sustainability throughout the lifecycle. It is still a challenge to accurately and efficiently evaluate the time-dependent reliability of engineering systems. This paper proposes a novel adaptive surrogate model method combining stochastic configuration network (SCN) and Kriging strategies to evaluate time-dependent reliability. SCN has accurate approximation ability and learning efficiency for strongly nonlinear systems that can overcome the conventional time-dependent reliability calculation, which is time-consuming and characterized by low accuracy. The proposed method first applies SCN to establish the response model of the performance function with respect to time and obtain the extreme value of the performance function. Then, Kriging is used to establish the extreme value model of the performance function with respect to the random variables based on the extreme value of performance function. The adaptive process considering the characteristics of random variables samples is adopted to update the extreme value model until the model meets the confidence target. Lastly, Monte Carlo simulation is employed for time-dependent reliability assessment based on the established extreme value model. Three example studies are used to demonstrate the effectiveness of the proposed approach for time-dependent reliability assessment.

关键词： Surrogate model randomized algorithm Stochastic configuration network Adaptive Kriging Time-dependent reliability

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：