We propose a fast algorithm for the calculation of the Wasserstein-1 distance, which is a particular type of optimal transport distance with transport cost homogeneous of degree one. Our algorithm is built on multilev...
详细信息
We propose a fast algorithm for the calculation of the Wasserstein-1 distance, which is a particular type of optimal transport distance with transport cost homogeneous of degree one. Our algorithm is built on multilevel primal-dual algorithms. Several numerical examples and a complexity analysis are provided to demonstrate its computational speed. On some commonly used image examples of size 512 x 512, the proposed algorithm gives solutions within 0.2 similar to 1.5 seconds on a single CPU, which is much faster than the state-of-the-art algorithms.
Hypergraph partitioning (HGP) is an NP-hard problem that occurs in many computer science applications where it is necessary to reduce large problems into a number of smaller, computationally tractable subproblems. Cur...
详细信息
Hypergraph partitioning (HGP) is an NP-hard problem that occurs in many computer science applications where it is necessary to reduce large problems into a number of smaller, computationally tractable subproblems. Current techniques use a multilevel approach wherein an initial partitioning is performed after compressing the hypergraph to a predetermined level. This level is typically chosen to produce very coarse hypergraphs in which heuristic algorithms are fast and effective. This paper presents a novel memetic algorithm which remains effective on larger initial hypergraphs. This enables the exploitation of information that can be lost during coarsening and results in improved final solution quality. We use this algorithm to present an empirical analysis of the space of possible initial hypergraphs in terms of its searchability at different levels of coarsening. We find that the best results arise at coarsening levels unique to each hypergraph. Based on this, we introduce an adaptive scheme that stops coarsening when the rate of information loss in a hypergraph becomes nonlinear and show that this produces further improvements. The results show that we have identified a valuable role for evolutionary algorithms within the current state-of-the-art HGP framework.
multilevel partitioning methods that are inspired by principles of multiscaling are the most powerful practical hypergraph partitioning solvers. Hypergraph partitioning has many applications in disciplines ranging fro...
详细信息
multilevel partitioning methods that are inspired by principles of multiscaling are the most powerful practical hypergraph partitioning solvers. Hypergraph partitioning has many applications in disciplines ranging from scientific computing to data science. In this paper we introduce the concept of algebraic distance on hypergraphs and demonstrate its use as an algorithmic component in the coarsening stage of multilevel hypergraph partitioning solvers. The algebraic distance is a vertex distance measure that extends hyperedge weights for capturing the local connectivity of vertices which is critical for hypergraph coarsening schemes. The practical effectiveness of the proposed measure and corresponding coarsening scheme is demonstrated through extensive computational experiments on a diverse set of problems. Finally, we propose a benchmark of hypergraph partitioning problems to compare the quality of other solvers.
Coupled multiphysics problems often give rise to interface conditions naturally formulated in fractional Sobolev spaces. Here, both positive and negative fractionality are common. When designing efficient solvers for ...
详细信息
Coupled multiphysics problems often give rise to interface conditions naturally formulated in fractional Sobolev spaces. Here, both positive and negative fractionality are common. When designing efficient solvers for discretizations of such problems it would therefore be useful to have a preconditioner for the fractional Laplacian. In this work, we develop an additive multigrid preconditioner for the fractional Laplacian with positive fractionality and show a uniform bound on the condition number. For the case of negative fractionality, we reuse the preconditioner developed for the positive fractionality and left-right multiply a regular Laplacian with a preconditioner with positive fractionality to obtain the desired negative fractionality. Implementational issues are out-lined in detail as the differences between the discrete operators and their corresponding matrices must be addressed when realizing these algorithms in code. We finish with some numerical experiments verifying the theoretical findings.
A new class of symmetric factored approximate inverses is proposed and used in conjunction with the Preconditioned Conjugate Gradient method for solving sparse symmetric linear systems. Additionally, a new hybrid two-...
详细信息
A new class of symmetric factored approximate inverses is proposed and used in conjunction with the Preconditioned Conjugate Gradient method for solving sparse symmetric linear systems. Additionally, a new hybrid two-level solver is proposed utilizing a block independent set reordering, in order to create the two level hierarchy. The Schur complement is formed explicitly by inverting the blocks created by reordering. Then, the preconditioned conjugate gradient method is used in conjunction with the symmetric factored approximate inverse to solve the reduced order linear system. Furthermore, numerical results on the performance and convergence behavior for solving various model problems are presented.
A randomized and a deterministic algorithm for the fast computation of impedance matrix blocks' low-rank factorization are contrasted. The deterministic algorithm is based on multilevel compression of non-uniforml...
详细信息
ISBN:
(纸本)9781538632840
A randomized and a deterministic algorithm for the fast computation of impedance matrix blocks' low-rank factorization are contrasted. The deterministic algorithm is based on multilevel compression of non-uniformly sampled phase-and amplitude-compensated interactions between clusters of source/observer basis/testing functions. The randomized algorithm is accelerated by using fast Fourier transform-based field evaluation. The algorithms' performance are compared for various classes of problem topology and algorithm parameters.
In orientation to new developments in evolutionary biology we propose an extension of evolutionary algorithms in two dimensions, the regulatory algorithm (RGA). It consists of two levels of vectors, the regulatory vec...
详细信息
In orientation to new developments in evolutionary biology we propose an extension of evolutionary algorithms in two dimensions, the regulatory algorithm (RGA). It consists of two levels of vectors, the regulatory vector and the structural vector. Each element of the regulatory vector is connected with one or several elements of the structural vector, but not vice versa. The connections can be interpreted as steering connections, the switching on or off of the structural elements and/or as switching orders for the structural elements. An RGA that operates with the usual genetic operators of mutation and crossover can be used for avoiding rules like penalty or default operators, it is in certain problems significantly faster than a standard genetic algorithm, and it is very suited when modeling and optimizing systems that consist themselves of different levels. Examples of RGA usage are shown, namely, the optimal dividing of socially deviant youths in a hostel, the optimal introduction of communication standards in information systems, and the allocation of employees to superiors by taking into regard the different personality types.
Two physics-based rank-revealing multilevel algorithms are presented to efficiently compute impedance matrix blocks' low-rank representations. Both algorithms rely on non-uniform sampling of phase-and amplitude-co...
详细信息
ISBN:
(纸本)9781509028528
Two physics-based rank-revealing multilevel algorithms are presented to efficiently compute impedance matrix blocks' low-rank representations. Both algorithms rely on non-uniform sampling of phase-and amplitude-compensated fields but use different auxiliary grids. The algorithms' computational costs and range of validity are compared.
An algorithm for the fast computation of the physical optics (PO) integral describing single bounce back scattering in near-field scenarios is presented. The algorithm is based on a multilevel computation of partial c...
详细信息
An algorithm for the fast computation of the physical optics (PO) integral describing single bounce back scattering in near-field scenarios is presented. The algorithm is based on a multilevel computation of partial contributions to the PO integral by hierarchically ordered subdomains. Phase- and amplitude-compensation of the partial contributions allows for their coarse sampling over non-uniform spherical grids. The solution is obtained by gradual aggregation of such partial contributions via interpolation on progressively denser grids. The computational complexity is further reduced by representation of small subdomains' contributions via their far-field patterns and transition to the near-field representations only at a higher level. Speed-up, accuracy, and error controllability are demonstrated.
We study the numerical integration of functions depending on an infinite number of variables. We provide lower error bounds for general deterministic algorithms and provide matching upper error bounds with the help of...
详细信息
We study the numerical integration of functions depending on an infinite number of variables. We provide lower error bounds for general deterministic algorithms and provide matching upper error bounds with the help of suitable multilevel algorithms and changing-dimension algorithms. More precisely, the spaces of integrands we consider are weighted, reproducing kernel Hilbert spaces with norms induced by an underlying anchored function space decomposition. Here the weights model the relative importance of different groups of variables. The error criterion used is the deterministic worst-case error. We study two cost models for function evaluations that depend on the number of active variables of the chosen sample points, and we study two classes of weights, namely product and order-dependent weights and the newly introduced finite projective dimension weights. We show for these classes of weights that multilevel algorithms achieve the optimal rate of convergence in the first cost model while changing-dimension algorithms achieve the optimal convergence rate in the second model. As an illustrative example, we discuss the anchored Sobolev space with smoothness parameter and provide new optimal quasi-Monte Carlo multilevel algorithms and quasi-Monte Carlo changing-dimension algorithms based on higher-order polynomial lattice rules.
暂无评论