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

algorithmICA 2009年第4期54卷 530-543页

作者： Liu, Yunlong Chen, Jianer Wang, Jianxin Cent S Univ Sch Informat Sci & Engn Changsha 410083 Peoples R China Hunan Normal Univ Sch Further Educ Changsha 410012 Peoples R China Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

The computational complexity of counting the number of matchings of size k in a given triple set has been open. It is conjectured that the problem is not fixed parameter tractable. In this paper, we present a fixed parameter tractable randomized approximation scheme (FPTRAS) for the problem. More precisely, we develop a randomized algorithm that, on given positive real numbers is an element of and delta, and a given set S of n triples and an integer k, produces a number h in time O(5.48(3k)n(2)ln(2/delta)/is an element of(2)) such that Prob[(1 - is an element of)h(0) <= h <= (1 + is an element of)h(0)] >= 1 - delta, where h(0) is the total number of matchings of size k in the triple set S. Our algorithm is based on the recent improved color-coding techniques and the Monte-Carlo self-adjusting coverage algorithm developed by Karp, Luby and Madras.

关键词： 3-D matching Parameterized algorithm Approximation algorithm randomized algorithm Counting complexity

来源：评论

学校读者我要写书评

暂无评论

Visibility testing and counting for uncertain segments

引用

THEORETICAL COMPUTER SCIENCE 2019年 779卷 1-7页

作者： Abam, Mohammad Ali Alipour, Sharareh Ghodsi, Mohammad Mahdian, Mohammad Sherif Univ Technol Comp Engn Dept Tehran Iran Inst Res Fundamental Sci IPM Sch Comp Sci Tehran Iran Google Res Mountain View CA 94043 USA

We study two well-known planar visibility problems, namely visibility testing and visibility counting, in a model where there is uncertainty about the input data. The standard versions of these problems are defined as follows: we are given a set S of n segments in R-2, and we would like to preprocess S so that we can quickly answer queries of the form: is the given query segment s is an element of S visible from the given query point q is an element of R-2 (for visibility testing) and how many segments in S are visible from the given query point q is an element of R-2 (for visibility counting). In our model of uncertainty, each segment may or may not exist, and if it does, it is located in one of finitely many possible locations, given by a discrete probability distribution. In this setting, the probabilistic visibility testing problem (PVTP, for short) is to compute the probability that a given segment s is an element of S is visible from a given query point q and the probabilistic visibility counting problem (PVCP, for short) is to compute the expected number of segments in S that are visible from a query point q. We first show that PVTP is #P-complete. In the special case where uncertainty is only about whether segments exist and not about their location, we show that PVTP is solvable in O(n logn) time. Our algorithm for PVTP combined with linearity of expectation gives an O(n(2) logn) time algorithm for PVCP. Using the algorithm for PVTP, together with a few old tricks, we can show that one can preprocess S in O(n(5) logn) time into a data structure of size O(n(4)), so that each PVTP query for a fixed segments can be answered in O (logn) time. We also give a faster 2-approximation algorithm for this problem. At the end, we improve the approximation factor of the algorithm. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Computational geometry Visibility randomized algorithm Approximation algorithm Probabilistic segments

来源：评论

学校读者我要写书评

暂无评论

Exact simulation of first exit times for one-dimensional diffusion processes

引用

ESAIM-MATHEMATICAL MODELLING AND NUMERICAL ANALYSIS-MODELISATION MATHEMATIQUE ET ANALYSE NUMERIQUE 2020年第3期54卷 811-844页

作者： Herrmann, Samuel Zucca, Cristina Univ Bourgogne Franche Comte CNRS UMR 5584 Inst Math Bourgogne F-21000 Dijon France Univ Turin Dept Math G Peano Via Carlo Alberto 10 I-10123 Turin Italy

The simulation of exit times for diffusion processes is a challenging task since it concerns many applications in different fields like mathematical finance, neuroscience, reliability horizontal ellipsis The usual procedure is to use discretization schemes which unfortunately introduce some error in the target distribution. Our aim is to present a new algorithm which simulates exactly the exit time for one-dimensional diffusions. This acceptance-rejection algorithm requires to simulate exactly the exit time of the Brownian motion on one side and the Brownian position at a given time, constrained not to have exit before, on the other side. Crucial tools in this study are the Girsanov transformation, the convergent series method for the simulation of random variables and the classical rejection sampling. The efficiency of the method is described through theoretical results and numerical examples.

关键词： Exit time Brownian motion diffusion processes Girsanov's transformation rejection sampling exact simulation randomized algorithm conditioned Brownian motion

来源：评论

学校读者我要写书评

暂无评论

Efficient methods for computing the reliability polynomials of graphs and complex networks

引用

JOURNAL OF SUPERCOMPUTING 2022年第7期78卷 9741-9781页

作者： Safaei, F. Akbar, R. Moudi, M. Shahid Beheshti Univ Fac Comp Sci & Engn Tehran Iran Univ Torbat Heydarieh Dept Comp Engn Torbat Heydarieh Razavi Khorasan Iran

Various methods have been proposed to evaluate the reliability of a graph, one of the most well known of which is the reliability polynomial, R(G, p). It is assumed that G(V, E) is a simple and unweighted connected graph whose nodes are perfect and edges are operational with an independent probability p. Thus, the edge reliability polynomial is a function of p of the number of network edges. There are various methods for calculating the coefficients of reliability polynomial, all of which are related to their recursive nature, which has led to an increase in their computational complexity. Therefore, if the difference between the number of links and nodes in the network exceeds a certain amount, the exact calculation of the coefficients R(G, p) is practically in the NP-hard complexity class. In this paper, while examining the problems in the previous methods, four new approaches for estimating the coefficients of reliability polynomial are presented. In the first approach, using an iterative method, the coefficients are estimated. This method, on average, has the same accuracy as common methods in the related studies. In addition, the second method as an intelligent scheme for integrating the values of coefficients has been proposed. The values of coefficients for smaller, larger, and finally intermediate indices have been determined with the help of this intelligent approach. Further, as a third proposed method, Benford's law is utilized to combine the coefficients. Finally, in the fourth approach, using the Legendre interpolation method, the coefficients are effectively estimated with an appropriate accuracy. To compare these approaches fairly and accurately with each other, they have been carried out on synthetic and real-world underlying graphs. Then, their efficiency and accuracy have been evaluated, compared, and analyzed according to the experimental results.

关键词： Network reliability Reliability polynomial Robustness measure Graph theory randomized algorithm Numerical analysis

来源：评论

学校读者我要写书评

暂无评论

randomized Quaternion QLP Decomposition for Low-Rank Approximation

引用

JOURNAL OF SCIENTIFIC COMPUTING 2022年第3期92卷 80-80页

作者： Ren, Huan Ma, Ru-Ru Liu, Qiaohua Bai, Zheng-Jian Xiamen Univ Sch Math Sci Xiamen 360015 Peoples R China Suzhou Univ Sci & Technol Sch Math Sci Suzhou 215009 Peoples R China Shanghai Univ Dept Math Shanghai 200444 Peoples R China Xiamen Univ Fujian Prov Key Lab Math Modeling & High Performa Xiamen 361005 Peoples R China

The low-rank approximation of a quaternion matrix has attracted growing attention in many applications including color image processing and signal processing. In this paper, based on quaternion normal distribution random sampling, we propose a randomized quaternion QLP decomposition algorithm for computing a low-rank approximation to a quaternion data matrix. For the theoretical analysis, we first present convergence results of the quaternion QLP decomposition, which provides slightly tighter upper bounds than the existing ones for the real QLP decomposition. Then, for the randomized quaternion QLP decomposition, the matrix approximation error and the singular value approximation error analyses are also established to show the proposed randomized algorithm can track the singular values of the quaternion data matrix with high probability. Finally, we present some numerical examples to illustrate the effectiveness and reliablity of the proposed algorithm.

关键词： Quaternion data matrix Low-rank approximation Quaternion QLP decomposition randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Infinite-Dimensional Quadrature and Approximation of Distributions

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2009年第4期9卷 391-429页

作者： Creutzig, Jakob Dereich, Steffen Mueller-Gronbach, Thomas Ritter, Klaus Tech Univ Berlin Fak 2 Inst Math D-10623 Berlin Germany Tech Univ Darmstadt Fachbereich Math D-64289 Darmstadt Germany Univ Magdeburg Fak Math Inst Math Stochast D-39016 Magdeburg Germany

We study numerical integration of Lipschitz functionals on a Banach space by means of deterministic and randomized (Monte Carlo) algorithms. This quadrature problem is shown to be closely related to the problem of quantization and to the average Kolmogorov widths of the underlying probability measure. In addition to the general setting, we analyze, in particular, integration with respect to Gaussian measures and distributions of diffusion processes. We derive lower bounds for the worst case error of every algorithm in terms of its cost, and we present matching upper bounds, up to logarithms, and corresponding almost optimal algorithms. As auxiliary results, we determine the asymptotic behavior of quantization numbers and Kolmogorov widths for diffusion processes.

关键词： Quadrature problem randomized algorithm Minimal error Wasserstein distance Functional quantization Average Kolmogorov width Multilevel Monte Carlo algorithm

来源：评论

学校读者我要写书评

暂无评论

Upper and lower bounds for selection on the mesh

引用

algorithmICA 1998年第1期20卷 1-30页

作者： Condon, A Narayanan, L CONCORDIA UNIV DEPT COMP SCIMONTREALPQ H3G 1M8CANADA

A distance-optimal algorithm for selection on the mesh has proved to be elusive, although distance-optimal algorithms for the related problems of routing and sorting have recently been discovered. In this paper we explain, using the notion of adaptiveness, why techniques used in the currently best selection algorithms cannot lead to a distance-optimal algorithm. For worst-case inputs we apply new techniques to improve the previous best upper bound of 1.22n of Kaklamanis et al. [7] to 1.15n. This improvement is obtained in part by increasing the adaptiveness of previous algorithms.

关键词： lower bound selection mesh randomized algorithm adaptiveness

来源：评论

学校读者我要写书评

暂无评论

A Unified Theorem on SDP Rank Reduction

引用

MATHEMATICS OF OPERATIONS RESEARCH 2008年第4期33卷 910-920页

作者： So, Anthony Man-Cho Ye, Yinyu Zhang, Jiawei Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China Stanford Univ Dept Management Sci & Engn Stanford CA 94305 USA NYU Stern Sch Business Dept Informat Operat & Management Sci New York NY 10012 USA

We consider the problem of finding a low-rank approximate solution to a system of linear equations in symmetric, positive semidefinite matrices, where the approximation quality of a solution is measured by its maximum relative deviation, both above and below, from the prescribed quantities. We show that a simple randomized polynomial-time procedure produces a low-rank solution that has provably good approximation qualities. Our result provides a unified treatment of and generalizes several well-known results in the literature. In particular, it contains as special cases the Johnson-Lindenstrauss lemma on dimensionality reduction, results on low-distortion embeddings into low-dimensional Euclidean space, and approximation results on certain quadratic optimization problems.

关键词： semidefinite programming low-rank matrices randomized algorithm metric embedding quadratic optimization

来源：评论

学校读者我要写书评

暂无评论

SPARSE APPROXIMATE MULTIFRONTAL FACTORIZATION WITH BUTTERFLY COMPRESSION FOR HIGH-FREQUENCY WAVE EQUATIONS

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2021年第5期43卷 S367-S391页

作者： Liu, Yang Ghysels, Pieter Claus, Lisa LI, Xiaoye Sherry Lawrence Berkeley Natl Lab Computat Res Div Berkeley CA 94720 USA

We present a fast and approximate multifrontal solver for large-scale sparse linear systems arising from finite-difference, finite-volume, or finite-element discretization of high-frequency wave equations. The proposed solver leverages the butterfly algorithm and its hierarchical matrix extension for compressing and factorizing large frontal matrices via graph distance guided entry evaluation or randomized matrix-vector multiplication-based schemes. Complexity analysis and numerical experiments demonstrate O(N log(2) N) computation and O(N) memory complexity when applied to an N x N sparse system arising from 3D high-frequency Helmholtz and Maxwell problems.

关键词： sparse direct solver multifrontal method butterfly algorithm randomized algorithm high-frequency wave equations Maxwell equation Helmholtz equation Poisson equation

来源：评论

学校读者我要写书评

暂无评论

Taylor Approximation for Chance Constrained Optimization Problems Governed by Partial Differential Equations with High-Dimensional Random Parameters

引用

SIAM-ASA JOURNAL ON UNCERTAINTY QUANTIFICATION 2021年第4期9卷 1381-1410页

作者： Chen, Peng Ghattas, Omar Univ Texas Austin Oden Inst Computat Engn & Sci Austin TX 78712 USA Univ Texas Austin Oden Inst Computat Engn & Sci Dept Mech Engn Austin TX 78712 USA Univ Texas Austin Dept Geol Sci Austin TX 78712 USA

We propose a fast and scalable optimization method to solve chance or probabilistic constrained optimization problems governed by partial differential equations (PDEs) with high-dimensional random parameters. To address the critical computational challenges of expensive PDE solution and highdimensional uncertainty, we construct surrogates of the constraint function by Taylor approximation, which relies on efficient computation of the derivatives, low-rank approximation of the Hessian, and a randomized algorithm for eigenvalue decomposition. To tackle the difficulty of the nondifferentiability of the inequality chance constraint, we use a smooth approximation of the discontinuous indicator function involved in the chance constraint, and we apply a penalty method to transform the inequality constrained optimization problem to an unconstrained one. Moreover, we design a gradient-based optimization scheme that gradually increases smoothing and penalty parameters to achieve convergence, for which we present an efficient computation of the gradient of the approximate cost functional by the Taylor approximation. Based on numerical experiments for a problem in optimal groundwater management, we demonstrate the accuracy of the Taylor approximation, its ability to greatly accelerate constraint evaluations, the convergence of the continuation optimization scheme, and the scalability of the proposed method in terms of the number of PDE solves with increasing random parameter dimension from one thousand to hundreds of thousands.

关键词： chance constrained optimization Taylor approximation randomized algorithm smooth approxi-mation penalty method Hessian

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：