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

Combinatorial algorithms enabling computational science: tales from the front

Journal of Physics: Conference Series 2006年第1期46卷

作者： Sanjukta Bhowmick Erik G Boman Karen Devine Assefaw Gebremedhin Bruce Hendrickson Paul Hovland Todd Munson Alex Pothen Mathematics and Computer Science Division Argonne National Laboratory USA Department of Applied Physics and Applied Mathematics Columbia University USA Discrete Algorithms and Math Department Sandia National Laboratories USA Computer Science Department Old Dominion University USA

Combinatorial algorithms have long played a crucial enabling role in scientific and engineering computations. The importance of discrete algorithms continues to grow with the demands of new applications and advanced architectures. This paper surveys some recent developments in this rapidly changing and highly interdisciplinary field.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Response surface models for hydrate prediction: Deterministic and probabilistic applications

Response surface models for hydrate prediction: Deterministi...

引用

12th International Conference on Multiphase Production Technology '05

作者： Averbuch, D. Gainville, M. Pierchon, A. Dejean, J.-P. Applied Mechanics Division Technology IFP France Computer Science and Applied Mathematics Division IFP France

ISBN: (纸本)1855980649

During the design phases of a Deep Offshore field development, a major issue in Flow Assurance is the prevention of Hydrates formation in the flowlines and risers. After designing the system, numerous multiphase flow and transient cool-down simulations are required, to account for different situations corresponding to several input parameters. This paper shows how to build efficiently Response Surfaces Models (RSM), which are simple mathematical models, accurately describing the critical time of hydrate formation, as a function of the input parameters, over a wide range of variation covering their variability. The obtained RSM can provide useful information for several applications such as sensitivity studies, in order to exhibit the most important input parameters, to reduce the calculation number, or to take into account uncertainty in the parameters. © BHR Group 2005 Multiphase Production Technology 12.

关键词： Hydrates

来源：评论

学校读者我要写书评

暂无评论

Concentration and relative entropy for compound poisson distributions

Concentration and relative entropy for compound poisson dist...

引用

2005 IEEE International Symposium on Information Theory, ISIT 05

作者： Madiman, M. Kontoyiannis, I. Division of Applied Mathematics Brown University Providence RI 02912 United States Division of Applied Mathematics Department of Computer Science Brown University Providence RI 02912 United States

ISBN: (纸本)0780391519

Using a simple inequality about the relative entropy, its so-called "tensorization property," we give a simple proof of a functional inequality which is satisfied by any compound Poisson distribution. This functional inequality belongs to the class of modified logarithmic Sobolev inequalities. We use it to obtain measure concentration bounds for compound Poisson distributions under a variety of assumptions on their tail behavior. In particular, we show how the celebrated "Herbst argument" can be modified to yield sub-exponential concentration bounds. For example, suppose Z is a compound Poisson random variable with values on the nonnegative integers, and let f be a function such that |f(k+1)- f(k)| &le 1 for all k. Then, if the base distribution of Z does not have a finite moment-generating function but has finite moments up to some order L > 1, we show that the probability that f(Z) exceeds its mean by a positive amount t or more decays approximately like (const)·t-L, where the constant is explicitly identified. This appears to be one of the very first examples of concentration bounds with power-law decay.

关键词： Information theory

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for minimum-weight vertex separators 05

Improved approximation algorithms for minimum-weight vertex ...

引用

13th Color Imaging Conference: Color science, Systems, Technologies, and Applications

作者： Feige, Uriel Hajiaghayi, Mohammadtaghi Lee, James R. Microsoft Research Department of Computer Science and Applied Mathematics Weizmann Institute Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology Computer Science Division U.C. Berkeley

ISBN: (纸本)9781581139600

We develop the algorithmic theory of vertex separators, and its relation to the embeddings of certain metric spaces. Unlike in the edge case, we show that embeddings into L1 (and even Euclidean embeddings) are insufficient, but that the additional structure provided by many embedding theorems does suffice for our purposes. We obtain an O(√log n) approximation formin-ratio vertex cuts in general graphs, based on a new semidefinite relaxation of the problem, and a tight analysis of the integrality gap which is shown to be Θ(√log n). We also prove various approximate max-flow/min-vertex-cut theorems, which in particular give a constant-factor approximation for min-ratio vertex cuts in any excluded-minor family of graphs. Previously, this was known only for planar graphs, and for general excluded-minor families the best-known ratio was O(log n). These results have a number of applications. We exhibit an O(√log n) pseudo-approximation for finding balanced vertex separators in general graphs. In fact, we achieve an approximation ratio of O(√log opt) where opt is the size of an optimal separator, improving over the previous best bound of O(log opt). Like-wise, we obtain improved approximation ratios for treewidth: In any graph of treewidth k, we show how to find a tree decomposition of width at most O(k√log k), whereas previous algorithms yielded O(k log k). For graphs excluding a fixed graph as a minor (which includes, e.g., bounded genus graphs), we give a constant-factor approximation for the treewidth;this can be used to obtain the first polynomial-time approximation schemes for problems like minimum feedback vertex set and minimum connected dominating set in such graphs. Copyright 2005 ACM.

关键词： Algorithms

来源：评论

学校读者我要写书评

暂无评论

Value function approximation with diffusion wavelets and Laplacian eigenfunctions

Value function approximation with diffusion wavelets and Lap...

引用

2005 Annual Conference on Neural Information Processing Systems, NIPS 2005

作者： Mahadevan, Sridhar Maggioni, Mauro Department of Computer Science University of Massachusetts Amherst MA 01003 United States Program in Applied Mathematics Department of Mathematics Yale University New Haven CT 06511 United States

ISBN: (纸本)9780262232531

We investigate the problem of automatically constructing efficient representations or basis functions for approximating value functions based on analyzing the structure and topology of the state space. In particular, two novel approaches to value function approximation are explored based on automatically constructing basis functions on state spaces that can be represented as graphs or manifolds: one approach uses the eigenfunctions of the Laplacian, in effect performing a global Fourier analysis on the graph;the second approach is based on diffusion wavelets, which generalize classical wavelets to graphs using multiscale dilations induced by powers of a diffusion operator or random walk on the graph. Together, these approaches form the foundation of a new generation of methods for solving large Markov decision processes, in which the underlying representation and policies are simultaneously learned.

关键词： Diffusion

来源：评论

学校读者我要写书评

暂无评论

Concentration and relative entropy for compound Poisson distributions

Concentration and relative entropy for compound Poisson dist...

引用

IEEE International Symposium on Information Theory

作者： M. Madiman I. Kontoyiannis Division of Applied Mathematics & Department of Computer Science Brown University Providence RI USA Division of Applied Mathematics Brown University Providence RI USA

ISBN: (纸本)0780391500

Using a simple inequality about the relative entropy, its so-called "tensorization property," we give a simple proof of a functional inequality which is satisfied by any compound Poisson distribution. This functional inequality belongs to the class of modified logarithmic Sobolev inequalities. We use it to obtain measure concentration bounds for compound Poisson distributions under a variety of assumptions on their tail behavior. In particular, we show how the celebrated "Herbst argument" can be modified to yield sub-exponential concentration bounds. For example, suppose Z is a compound Poisson random variable with values on the nonnegative integers, and let f be a function such that |f(k+1) - f(k)| les 1 for all k. Then, if the base distribution of Z does not have a finite moment-generating function but has finite moments up to some order L > 1, we show that the probability that f(Z) exceeds its mean by a positive amount t or more decays approximately like (const)middott -L , where the constant is explicitly identified. This appears to be one of the very first examples of concentration bounds with power-law decay

关键词： Entropy Random variables mathematics computer science Probability distribution Information geometry Functional analysis Algorithm design and analysis Physics Statistical analysis

来源：评论

学校读者我要写书评

暂无评论

Filtering: the case for "noisier" data

Filtering: the case for "noisier" data

引用

IEEE (first ITW conference of the year) Information Theory Workshop (ITW)

作者： B. Lucena I. Kontoyiannis Division of Computer Science University of California Berkeley CA USA Division of Applied Mathematics Department of Computer Science Brown University Providence RI USA

Suppose there is some discrete variable X of interest, which can only be observed after passing through 2 channels (Q and R). You are limited to n noisy observations of X and then must estimate the value of X. Your one control is a parameter k which determines the level of correlation in your observed data. Specifically, X is first transmitted through the channel Q n/k times to yield variables Y/sub 1/,..., Y/sub n/k/ and then each Y/sub i/ is transmitted through channel R k times to yield variables Z/sub i/,/sub 1/,..., Z/sub I,k/. How should k be chosen to maximize the probability of successfully guessing the correct value of X? While k /spl equiv/ 1 yields data points Z/sub i,1/ which are conditionally independent given the value of X, we find that this does not always mean that k /spl equiv/ 1 is the optimal choice. In fact, many simple situations yield cases where the optimal value of k is greater than 1. We explore this phenomenon and present both theoretical and empirical results.

关键词： Filtering computer aided software engineering Character generation Testing computer science Mutual information mathematics Electronic mail Memoryless systems Maximum likelihood estimation

来源：评论

学校读者我要写书评

暂无评论

Value function approximation with diffusion wavelets and Laplacian eigenfunctions 05

Value function approximation with diffusion wavelets and Lap...

引用

Proceedings of the 19th International Conference on Neural Information Processing Systems

作者： Sridhar Mahadevan Mauro Maggioni Department of Computer Science University of Massachusetts Amherst MA Program in Applied Mathematics Department of Mathematics Yale University New Haven CT

We investigate the problem of automatically constructing efficient representations or basis functions for approximating value functions based on analyzing the structure and topology of the state space. In particular, two novel approaches to value function approximation are explored based on automatically constructing basis functions on state spaces that can be represented as graphs or manifolds: one approach uses the eigenfunctions of the Laplacian, in effect performing a global Fourier analysis on the graph; the second approach is based on diffusion wavelets, which generalize classical wavelets to graphs using multiscale dilations induced by powers of a diffusion operator or random walk on the graph. Together, these approaches form the foundation of a new generation of methods for solving large Markov decision processes, in which the underlying representation and policies are simultaneously learned.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Hybrid Schwarz-multigrid methods for the spectral element method: Extensions to Navier-Stokes

引用

Lecture Notes in Computational science and Engineering 2005年 40卷 35-49页

作者： Fischer, Paul F. Lottes, James W. Argonne National Laboratory Mathematics and Computer Science Division United States University of Illinois Dept. of Theoretical and Applied Mechanics United States

ISBN: (纸本)3540225234

The performance of multigrid methods for the standard Poisson problem and for the consistent Poisson problem arising in spectral element discretizations of the Navier-Stokes equations is investigated. It is demonstrated that overlapping additive Schwarz methods are effective smoothers, provided that the solution in the overlap region is weighted by the inverse counting matrix. It is also shown that spectral element based smoothers are superior to those based upon finite element discretizations. Results for several large 3D Navier-Stokes applications are presented.

关键词： Navier Stokes equations

来源：评论

学校读者我要写书评

暂无评论

Mutual information, synergy and some curious phenomena for simple channels

Mutual information, synergy and some curious phenomena for s...

引用

IEEE International Symposium on Information Theory

作者： I. Kontoyiannis B. Lucena Div of Applied Mathematics & Dpt of Computer Science Brown University Providence RI USA Division of Computer Science University of California Berkeley Berkeley CA USA

ISBN: (纸本)0780391500

Suppose we are allowed to observe two equally noisy versions of some signal X, where the level of the noise is fixed. We are given a choice: we can either observe two independent noisy versions of X, or two correlated ones. We show that, contrary to what classical statistical intuition suggests, it is often the case that correlated data is more valuable than independent data. We investigate this phenomenon in a variety of contexts, we give numerous examples for standard families of channels, and we present general sufficient conditions for deciding this dilemma. One of these conditions draws an interesting connection with the information-theoretic notion of "synergy," which has received a lot of attention in the neuroscience literature recently

关键词： Mutual information Testing computer science Noise level mathematics Sufficient conditions Neuroscience Broadcasting Relays Sampling methods

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：