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

Parsimonious reconstruction of network evolution

学校读者我要写书评

暂无评论

Parsimonious reconstruction of network evolution

Lecture Notes in Computer Science

作者： Patro, Rob Sefer, Emre Malin, Justin Marçais, Guillaume Navlakha, Saket Kingsford, Carl Center for Bioinformatics and Computational Biology University of Maryland College Park MD 20742 United States Department of Computer Science University of Maryland College Park MD 20742 United States Computational Biology Bioinformatics and Genomics Concentration Biological Sciences Graduate Program University of Maryland College Park MD 20742 United States Program in Applied Mathematics Statistics and Scientific Computation University of Maryland College Park MD 20742 United States School of Computer Science Carnegie Mellon University Pittsburgh PA 15213 United States

ISBN: (纸本)9783642230370

We consider the problem of reconstructing a maximally parsimonious history of network evolution under models that support gene duplication and loss and independent interaction gain and loss. We introduce a combinatorial framework for encoding network histories, and we give a fast procedure that, given a set of duplication histories, in practice finds network histories with close to the minimum number of interaction gain or loss events. In contrast to previous studies, our method does not require knowing the relative ordering of unrelated duplication events. Results on simulated histories suggest that common ancestral networks can be accurately reconstructed using this parsimony approach. © 2011 Springer-Verlag.

关键词： Genes

Multilevel quasi-Monte Carlo for random elliptic eigenvalue problems II: Efficient algorithms and numerical results

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Gilbert, Alexander D. Scheichl, Robert School of Mathematics and Statistics University of New South Wales SydneyNSW2052 Australia Institute for Applied Mathematics Interdisciplinary Centre for Scientific Computing Universität Heidelberg Heidelberg69120 Germany Department of Mathematical Sciences University of Bath BathBA2 7AY United Kingdom

Stochastic PDE eigenvalue problems often arise in the field of uncertainty quantification, whereby one seeks to quantify the uncertainty in an eigenvalue, or its eigenfunction. In this paper we present an efficient multilevel quasi-Monte Carlo (MLQMC) algorithm for computing the expectation of the smallest eigenvalue of an elliptic eigenvalue problem with stochastic coefficients. Each sample evaluation requires the solution of a PDE eigenvalue problem, and so tackling this problem in practice is notoriously computationally difficult. We speed up the approximation of this expectation in four ways: we use a multilevel variance reduction scheme to spread the work over a hierarchy of FE meshes and truncation dimensions;we use QMC methods to efficiently compute the expectations on each level;we exploit the smoothness in parameter space and reuse the eigenvector from a nearby QMC point to reduce the number of iterations of the eigensolver;and we utilise a two-grid discretisation scheme to obtain the eigenvalue on the fine mesh with a single linear solve. The full error analysis of a basic MLQMC algorithm is given in the companion paper [Gilbert and Scheichl, 2022], and so in this paper we focus on how to further improve the efficiency and provide theoretical justification for using nearby QMC points and two-grid methods. Numerical results are presented that show the efficiency of our algorithm, and also show that the four strategies we employ are complementary. Copyright © 2021, The Authors. All rights reserved.

关键词： Eigenvalues and eigenfunctions

Multilevel quasi-Monte Carlo for random elliptic eigenvalue problems I: Regularity and error analysis

学校读者我要写书评

暂无评论

arXiv 2020年

Stochastic PDE eigenvalue problems are useful models for quantifying the uncertainty in several applications from the physical sciences and engineering, e.g., structural vibration analysis, the criticality of a nuclear reactor or photonic crystal structures. In this paper we present a multilevel quasi-Monte Carlo (MLQMC) method for approximating the expectation of the minimal eigenvalue of an elliptic eigenvalue problem with coefficients that are given as a series expansion of countably-many stochastic parameters. The MLQMC algorithm is based on a hierarchy of discretisations of the spatial domain and truncations of the dimension of the stochastic parameter domain. To approximate the expectations, randomly shifted lattice rules are employed. This paper is primarily dedicated to giving a rigorous analysis of the error of this algorithm. A key step in the error analysis requires bounds on the mixed derivatives of the eigenfunction with respect to both the stochastic and spatial variables simultaneously. Under stronger smoothness assumptions on the parametric dependence, our analysis also extends to multilevel higher-order quasi-Monte Carlo rules. An accompanying paper [Gilbert and Scheichl, 2022], focusses on practical extensions of the MLQMC algorithm to improve efficiency, and presents numerical results. Copyright © 2020, The Authors. All rights reserved.

关键词： Error analysis

Bounding the spectral gap for an elliptic eigenvalue problem with uniformly bounded stochastic coefficients

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Gilbert, A.D. Graham, I.G. Scheichl, R. Sloan, I.H. Institute for Applied Mathematics Interdisciplinary Center for Scientific Computing Universität Heidelberg Heidelberg69120 Germany Department of Mathematical Sciences University of Bath BathBA2 7AY United Kingdom School of Mathematics and Statistics University of New South Wales SydneyNSW2052 Australia

A key quantity that occurs in the error analysis of several numerical methods for eigenvalue problems is the distance between the eigenvalue of interest and the next nearest eigenvalue. When we are interested in the smallest or fundamental eigenvalue, we call this the spectral or fundamental gap. In a recent manuscript [Gilbert et al., https://***/abs/1808.02639], the current authors, together with Frances Kuo, studied an elliptic eigenvalue problem with homogeneous Dirichlet boundary conditions, and with coefficients that depend on an infinite number of uniformly distributed stochastic parameters. In this setting, the eigenvalues, and in turn the eigenvalue gap, also depend on the stochastic parameters. Hence, for a robust error analysis one needs to be able to bound the gap over all possible realisations of the parameters, and because the gap depends on infinitely-many random parameters, this is not trivial. This short note presents, in a simplified setting, an important result that was shown in the paper above. Namely, that, under certain decay assumptions on the coefficient, the spectral gap of such a random elliptic eigenvalue problem can be bounded away from 0, uniformly over the entire infinite-dimensional parameter space. Copyright © 2019, The Authors. All rights reserved.

关键词： Eigenvalues and eigenfunctions

Analysis of quasi-Monte Carlo methods for elliptic eigenvalue problems with stochastic coefficients

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Gilbert, A.D. Graham, I.G. Kuo, F.Y. Scheichl, R. Sloan, I.H. Institute for Applied Mathematics Interdisciplinary Center for Scientific Computing Universität Heidelberg Heidelberg69120 Germany Department of Mathematical Sciences University of Bath BathBA2 7AY United Kingdom School of Mathematics and Statistics University of New South Wales SydneyNSW2052 Australia

We consider the forward problem of uncertainty quantification for the generalised Dirichlet eigenvalue problem for a coercive second order partial differential operator with random coefficients, motivated by problems in structural mechanics, photonic crystals and neutron diffusion. The PDE coefficients are assumed to be uniformly bounded random fields, represented as infinite series parametrised by uniformly distributed i.i.d. random variables. The expectation of the fundamental eigenvalue of this problem is computed by (a) truncating the infinite series which define the coefficients;(b) approximating the resulting truncated problem using lowest order conforming finite elements and a sparse matrix eigenvalue solver;and (c) approximating the resulting finite (but high dimensional) integral by a randomly shifted quasi-Monte Carlo lattice rule, with specially chosen generating vector. We prove error estimates for the combined error, which depend on the truncation dimension s, the finite element mesh diameter h, and the number of quasi-Monte Carlo samples N. Under suitable regularity assumptions, our bounds are of the particular form O(h2+N-1+δ), where δ > 0 is arbitrary and the hidden constant is independent of the truncation dimension, which needs to grow as h → 0 and N → ∞. As for the analogous PDE source problem, the conditions under which our error bounds hold depend on a parameter p ∈ (0, 1) representing the summability of the terms in the series expansions of the coefficients. Although the eigenvalue problem is nonlinear, which means it is generally considered harder than the source problem, in almost all cases (p ≠ 1) we obtain error bounds that converge at the same rate as the corresponding rate for the source problem. The proof involves a detailed study of the regularity of the fundamental eigenvalue as a function of the random parameters. As a key intermediate result in the analysis, we prove that the spectral gap (between the fundamental and the second eigen

关键词： Eigenvalues and eigenfunctions

Preconditioners for regularized image superresolution

学校读者我要写书评

暂无评论

Preconditioners for regularized image superresolution

International Conference on Acoustics, Speech, and Signal Processing (ICASSP)

作者： N. Nguyan G. Golub P. Milanfar Sci. Comput. & Comput. Math. Program Stanford Univ. CA USA Scientific Computing and Computational Mathematics Program University of Stanford Stanford CA USA Applied Electromagnetics Lab SRI International Inc. Menlo Park CA USA

Superresolution reconstruction produces a high resolution image from a set of low resolution images. Previous work on superresolution had not adequately addressed the computational issues for this problem. In this paper, we propose efficient block circulant preconditioners for solving the regularized superresolution problem by conjugate gradients. The effectiveness of the preconditioners is demonstrated with superresolution results for a simulated image sequence and a FLIR image sequence.

关键词： Image resolution Layout Spatial resolution Pixel Image reconstruction Image sequences Motion estimation Solids Equations scientific computing

Sparse and switching infinite horizon optimal control with nonconvex penalizations

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Kalise, Dante Kunisch, Karl Rao, Zhiping Department of Mathematics Imperial College London South Kensington Campus LondonSW7 2AZ United Kingdom Institute for Mathematics and Scientific Computing University of Graz Heinrichstraße 36 GrazA-8010 Austria Radon Institute of Computational and Applied Mathematics Austrian Academy of Sciences School of Mathematics and Statistics Wuhan University Wuhan Hubei430072 China

A class of infinite horizon optimal control problems involving mixed quasi-norms of Lp-type cost functionals for the controls is discussed. These functionals enhance sparsity and switching properties of the optimal controls. The existence of optimal controls and their structural properties are analyzed on the basis of first order optimality conditions. A dynamic programming approach is used for numerical realization.93D15, 93B52, 93C05, 93C20 Copyright © 2018, The Authors. All rights reserved.

关键词： Dynamic programming

An Energy-Stable Finite Element Method for Nonlinear Maxwell's Equations

学校读者我要写书评

暂无评论

SSRN

SSRN 2022年

作者： Li, Lingxiao Lyu, Maohui Zheng, Weiying School of Mathematics and Statistics Henan University Kaifeng475004 China Center for Applied Mathematics of Henan Province Henan University Zhengzhou450046 China LSEC NCMIS Institute of Computational Mathematics and Scientific/Engineering Computing Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing100190 China School of Mathematical Science University of Chinese Academy of Sciences Beijing100049 China

In this paper, we consider the three-dimensional (3D) nonlinear Maxwell’s equations in an optical medium characterized by the linear Lorentz dispersion, the nonlinear Kerr effect, and the delayed Raman scattering. By introducing auxiliary variables, we propose a fully-discrete and energy-stable finite element method for the nonlinear problem. The discrete scheme is unconditionally stable and admits second-order convergence. To solve the nonlinear discrete problem, we propose a Newton-Krylov iterative method, where the linearized algebraic problems are solved with a preconditioned GMRES method based on the auxiliary space preconditioning for Maxwell’s equations. Numerical experiment for a spatial soliton shows agreements with the two-dimensional numerical simulations in the literature. Moreover, we also demonstrate the efficiency and parallel scalability of the finite element method numerically on 1–512 computer processors. © 2022, The Authors. All rights reserved.

关键词： Finite element method

MG-GNN: Multigrid Graph Neural Networks for Learning Multilevel Domain Decomposition Methods

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Taghibakhshi, Ali Nytko, Nicolas Zaman, Tareq Uz MacLachlan, Scott Olson, Luke N. West, Matthew Department of Mechanical Science and Engineering University of Illinois Urbana-Champaign United States Department of Computer Science University of Illinois Urbana-Champaign United States Scientific Computing Program Memorial University of Newfoundland Canada Department of Mathematics and Statistics Memorial University of Newfoundland Canada

Domain decomposition methods (DDMs) are popular solvers for discretized systems of partial differential equations (PDEs), with one-level and multilevel variants. These solvers rely on several algorithmic and mathematical parameters, prescribing overlap, subdomain boundary conditions, and other properties of the DDM. While some work has been done on optimizing these parameters, it has mostly focused on the one-level setting or special cases such as structured-grid discretizations with regular subdomain construction. In this paper, we propose multigrid graph neural networks (MG-GNN), a novel GNN architecture for learning optimized parameters in two-level DDMs. We train MG-GNN using a new unsupervised loss function, enabling effective training on small problems that yields robust performance on unstructured grids that are orders of magnitude larger than those in the training set. We show that MG-GNN outperforms popular hierarchical graph network architectures for this optimization and that our proposed loss function is critical to achieving this improved performance. © 2023, CC BY.

关键词： Domain decomposition methods