Search

We describe a practical algorithm for computing normal forms for semigroups and monoids with finite presentations satisfying so-called small overlap conditions. Small overlap conditions are natural conditions on the relations in a presentation, which were introduced by J. H. Remmers and subsequently studied extensively by M. Kambites. Presentations satisfying these conditions are ubiquitous; Kambites showed that a randomly chosen finite presentation satisfies the C (4) condition with probability tending to 1 as the sum of the lengths of relation words tends to infinity. Kambites also showed that several key problems for finitely presented semigroups and monoids are tractable in C (4) monoids: the word problem is solvable in O (min ⁡ { | u | , | v | }) time in the size of the input words u and v ; the uniform word problem for 〈 A | R 〉 is solvable in O (N 2 min ⁡ { | u | , | v | }) where N is the sum of the lengths of the words in R ; and a normal form for any given word u can be found in O (| u |) time. Although Kambites' algorithm for solving the word problem in C (4) monoids is highly practical, it appears that the coefficients in the linear time algorithm for computing normal forms are too large in practice. In this paper, we present an algorithm for computing normal forms in C (4) monoids that has time complexity O (| u | 2) for input word u , but where the coefficients are sufficiently small to allow for practical computation. Additionally, we show that the uniform word problem for small overlap monoids can be solved in O (N min ⁡ { | u | , | v | }) time. [ABSTRACT FROM AUTHOR]

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance and secure message distribution. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. Kao et al. (2019) [18] proposed an algorithm to construct independent spanning trees in bubble-sort networks. The algorithm is executed in a recursive function and thus is hard to parallelize. In this paper, we focus on the problem of constructing ISTs in bubble-sort networks B n and present a non-recursive algorithm. Our approach can be fully parallelized, i.e., every vertex can determine its parent in each spanning tree in constant time. This solves the open problem from the paper by Kao et al. Furthermore, we show that the total time complexity O (n ⋅ n !) of our algorithm is asymptotically optimal, where n is the dimension of B n and n ! is the number of vertices of the network. • We present an algorithm for constructing multiple independent spanning trees in bubble-sort networks. • Our approach can be fully parallelized, thus solving an open problem from Kao et al. (2019). • We show that the total time complexity of our algorithm is asymptotically optimal. [ABSTRACT FROM AUTHOR]

The performance of collective communication operations determines the overall performance of MPI applications. Different algorithms have been developed and implemented for each MPI collective operation, but none proved superior in all situations. Therefore, MPI implementations have to solve the problem of selecting the optimal algorithm for the collective operation depending on the platform, the number of processes involved, the message size(s), etc. The current solution method is purely empirical. Recently, an alternative solution method using analytical performance models of collective algorithms has been proposed and proved both accurate and efficient for one-process-per-CPU configurations. The method derives the analytical performance models of algorithms from their code implementation rather than from high-level mathematical definitions, and estimates the parameters of the models separately for each algorithm. The method is network and topology oblivious and uses the Hockney model for point-to-point communications. In this paper, we extend that selection method to the case of clusters of multi-core processors, where each core of the platform runs a process of the MPI application. We present the proposed approach using Open MPI broadcast algorithms, and experimentally validate it on three different clusters of multi-core processors, Grisou, Gros and MareNostrum4. • A novel model-based method for runtime selection of optimal collective algorithms. • Application of the proposed method to the Open MPI broadcast algorithms. • Experimental validation of the method on two modern multi-core clusters. [ABSTRACT FROM AUTHOR]

Sparse polynomial interpolation, sparse linear system solving or modular rational reconstruction are fundamental problems in Computer Algebra. They come down to computing linear recurrence relations of a sequence with the Berlekamp–Massey algorithm. Likewise, sparse multivariate polynomial interpolation and multidimensional cyclic code decoding require guessing linear recurrence relations of a multivariate sequence. Several algorithms solve this problem. The so-called Berlekamp–Massey–Sakata algorithm (1988) uses polynomial additions and shifts by a monomial. The Scalar-FGLM algorithm (2015) relies on linear algebra operations on a multi-Hankel matrix, a multivariate generalization of a Hankel matrix. The Artinian Gorenstein border basis algorithm (2017) uses a Gram-Schmidt process. We propose a new algorithm for computing the Gröbner basis of the ideal of relations of a sequence based solely on multivariate polynomial arithmetic. This algorithm allows us to both revisit the Berlekamp–Massey–Sakata algorithm through the use of polynomial divisions and to completely revise the Scalar-FGLM algorithm without linear algebra operations. A key observation in the design of this algorithm is to work on the mirror of the truncated generating series allowing us to use polynomial arithmetic modulo a monomial ideal. It appears to have some similarities with Padé approximants of this mirror polynomial. As an addition from the paper published at the ISSAC conference, we give an adaptive variant of this algorithm taking into account the shape of the final Gröbner basis gradually as it is discovered. The main advantage of this algorithm is that its complexity in terms of operations and sequence queries only depends on the output Gröbner basis. All these algorithms have been implemented in Maple and we report on our comparisons. [ABSTRACT FROM AUTHOR]

Failure detectors (FD)s are celebrated for their modularity in solving distributed problems. Algorithms are constructed using FD building blocks. Synchrony assumptions to implement FDs are studied separately and are typically expressed as eventual guarantees that need to hold, after some point in time, forever and deterministically. But in practice, they may hold only probabilistically and temporarily. This paper studies FDs in a realistic system N , where asynchrony is inflicted by probabilistic synchronous communication. We first address a problem with ⋄ S , the weakest FD to solve consensus: an implementation of "consensus with probability 1" is possible in N without randomness in the algorithm, while an implementation of " ⋄ S with probability 1" is impossible in N. We introduce ⋄ S ⁎ , a new FD with probabilistic and temporal accuracy. We prove that ⋄ S ⁎ (i) is implementable in N and (ii) can replace ⋄ S , in several existing deterministic consensus algorithms that use ⋄ S , to yield an algorithm that solves "consensus with probability 1". We extend our results to other FD classes, e.g., ⋄ P , and to a larger set of problems (beyond consensus), which we call decisive problems. • We propose a way to preserve the usefulness of failure detectors (FD)s as software building blocks in probabilistically synchronous systems as (N). • We define <>S*, a probabilistic FD with accuracy ensured for arbitrarily long finite periods and that can be implemented in systems as N. • We present an optimal <>S* algorithm, which achieves in the best case the lowest communication overhead (C-1) compared to all known <>S algorithms. • We extend our FD definitions for other FD classes and other distributed computing problems besides consensus, which we call decisive problems. • We encapsulate the randomization of probabilistic links in the very abstraction of FD, without affecting deterministic algorithms built on top. [ABSTRACT FROM AUTHOR]

Our goal in the paper is to address the following problem: From an unknown matrix, we are given inner products of that matrix with a set of prescribed matrices, and wish to find the unknown matrix. We shall consider this problem by using the notion of minimal norm interpolation. A fixed-point proximity algorithm for solving this problem will be developed. [ABSTRACT FROM AUTHOR]

Abstract We analyze a new random algorithm for numerical integration of d -variate functions over [ 0 , 1 ] d from a weighted Sobolev space with dominating mixed smoothness α ≥ 0 and product weights 1 ≥ γ 1 ≥ γ 2 ≥ ⋯ > 0 , where the functions are continuous and periodic when α > 1 ∕ 2. The algorithm is based on rank-1 lattice rules with a random number of points n. For the case α > 1 ∕ 2 , we prove that the algorithm achieves almost the optimal order of convergence of O (n − α − 1 ∕ 2) , where the implied constant is independent of the dimension d if the weights satisfy ∑ j = 1 ∞ γ j 1 ∕ α < ∞. The same rate of convergence holds for the more general case α > 0 by adding a random shift to the lattice rule with random n. This shows, in particular, that the exponent of strong tractability in the randomized setting equals 1 ∕ (α + 1 ∕ 2) , if the weights decay fast enough. We obtain a lower bound to indicate that our results are essentially optimal. This paper is a significant advancement over previous related works with respect to the potential for implementation and the independence of error bounds on the problem dimension. Other known algorithms which achieve the optimal error bounds, such as those based on Frolov's method, are very difficult to implement especially in high dimensions. Here we adapt a lesser-known randomization technique introduced by Bakhvalov in 1961. This algorithm is based on rank-1 lattice rules which are very easy to implement given the integer generating vectors. A simple probabilistic approach can be used to obtain suitable generating vectors. [ABSTRACT FROM AUTHOR]

Abstract The level set method for modeling multi-fluid interfaces gives a simple approach for the simulation of multiphase flow problems. However, many of the components of this method, such as the redistancing of the level set function and discretization of the singular surface tension force, become more difficult on unstructured meshes in a control volume framework; furthermore, these operations are shown to lead to errors in conservation of mass of the individual phases, as well as unphysical currents near the interface. This paper presents a novel formulation for the level set method combined with a balanced-force algorithm using a control volume finite element method (CVFEM) for unstructured grids. A diffuse interface description is used, allowing a straightforward inclusion of surface tension forces; we show that by consistently evaluating the pressure gradient and surface tension, we are able to discretely balance these two forces and suppress any parasitic currents given a prescribed curvature. By converting the redistancing equation to a form that is suitable for CVFEM and enforcing a constraint directly linked with the phase fraction in each cell, we are able conserve mass and preserve the shape of the interface to a high degree of accuracy in multiphase flow problems with high density and viscosity ratios. The accuracy of the of our proposed method is assessed by comparing with benchmark results from the literature. Highlights • A novel level set formulation utilizing CVFEM is proposed. • A balanced-force algorithm is formulated for purely unstructured meshes. • The redistancing equation is reformulated to allow higher order upwinding methods. • A new constraint is introduced to preserve the shape of the interface. • Benchmark examples show convergence for high density and viscosity ratio problems. [ABSTRACT FROM AUTHOR]

This paper deals with improvements of the Trudinger–Moser inequality related to the operator Q V ( u ) : = − Δ n u + V ( x ) | u | n − 2 u , where n ≥ 2 and the potential V : R n → R belongs to a class of nonnegative and continuous functions. Precisely, under suitable assumptions on V we consider the subspace E : = { u ∈ W 1 , n ( R n ) : ∫ R n V ( x ) | u | n d x < ∞ } endowed with the norm ‖ u ‖ : = [ ∫ R n ( | ∇ u | n + V ( x ) | u | n ) d x ] 1 / n and we prove that if ( u k ) is a sequence in E such that ‖ u k ‖ = 1 , u k ⇀ u ≢ 0 in E and 0 < p < p n ( u ) : = β n ( 1 − ‖ u ‖ n ) − 1 / ( n − 1 ) , then ( ⁎ ) sup k ⁡ ∫ R n Ψ ( p | u k | n / ( n − 1 ) ) d x < ∞ , where Ψ ( t ) : = e t − ∑ i = 0 n − 2 t i i ! , β n : = n ω n − 1 1 / ( n − 1 ) and ω n − 1 is the measure of the unit sphere in R n . Furthermore, p n ( u ) is sharp in the sense that there exists a sequence ( u k ) ⊂ E satisfying ‖ u k ‖ = 1 and u k ⇀ u ≢ 0 in E such that the supremum (⁎) is infinite for p ≥ p n ( u ) . As an application of the previous result we prove the following sharp form of the Trudinger–Moser inequality for the subspace E . Considering ℓ ( α ) : = sup { u ∈ E : ‖ u ‖ = 1 } ⁡ ∫ R n Ψ ∘ ν α ( u ) d x , where ν α ( u ) : = β n ( 1 + α ‖ u ‖ n n ) 1 / ( n − 1 ) | u | n / ( n − 1 ) , assuming some conditions of symmetry on V it is established (1) for 0 ≤ α < λ 1 ( V ) we have ℓ ( α ) < ∞ , (2) for α ≥ λ 1 ( V ) , ℓ ( α ) = ∞ and (3) moreover, we prove that for 0 ≤ α < λ 1 ( V ) , an extremal function for ℓ ( α ) exists. Here λ 1 ( V ) denotes the first eigenvalue of Q V ( u ) . [ABSTRACT FROM AUTHOR]

Martin-Löf defined algorithmic randomness, the use of martingales in this definition and several variants were explored by Schnorr, and Lutz introduced resource-bounded randomness. Ambos-Spies et al. have studied resource-bounded randomness under time-bounds and have shown that resource-bounded randomness implies resource-bounded genericity. While the genericity of Ambos-Spies is based on time-bound on finite-extension strategy, the genericity of Dowd, the main topic of this paper, is based on an analogy of the forcing theorem. For a positive integer r , an oracle D is r -generic in the sense of Dowd ( r -Dowd) if the following holds: If a certain formula F on an exponential-sized portion of D is a tautology then a polynomial-sized subfunction of D forces F to be a tautology. Here, r is the number of occurrences of query symbols in F . The relationship between resource-bounded randomness and Dowd-type genericity has been not clear so far. We show that there exists a primitive recursive function t ( n ) with the following property: Every t ( n ) -random set is r -Dowd for each positive integer r . A proof is done by means of constructing resource-bounded martingales. In our former paper, we left an open problem whether there exists a primitive recursive set which is r -Dowd for every positive integer r . In our recent work, we give an affirmative answer to the problem. The main theorem of the present paper gives an alternative proof of the affirmative answer. [ABSTRACT FROM AUTHOR]

Many problems on graphs can be expressed in the following language: given a graph G = ( V , E ) and a terminal set T ⊆ V , find a minimum size set S ⊆ V which intersects all “structures” (such as cycles or paths) passing through the vertices in T . We refer to this class of problems as terminal set problems. In this paper, we introduce a general method to obtain faster exact exponential time algorithms for several terminal set problems. In the process, we break the O ⁎ ( 2 n ) barrier for the classic Node Multiway Cut , Directed Unrestricted Node Multiway Cut and Directed Subset Feedback Vertex Set problems. [ABSTRACT FROM AUTHOR]

Abstract: For many of the unsolved problems concerning cycles and matchings in graphs it is known that it is sufficient to prove them for snarks, the class of non-trivial 3-regular graphs which cannot be 3-edge coloured. In the first part of this paper we present a new algorithm for generating all non-isomorphic snarks of a given order. Our implementation of the new algorithm is 14 times faster than previous programs for generating snarks, and 29 times faster for generating weak snarks. Using this program we have generated all non-isomorphic snarks on vertices. Previously lists up to vertices have been published. In the second part of the paper we analyze the sets of generated snarks with respect to a number of properties and conjectures. We find that some of the strongest versions of the cycle double cover conjecture hold for all snarks of these orders, as does Jaegerʼs Petersen colouring conjecture, which in turn implies that Fulkersonʼs conjecture has no small counterexamples. In contrast to these positive results we also find counterexamples to eight previously published conjectures concerning cycle coverings and the general cycle structure of cubic graphs. [Copyright &y& Elsevier]

Abstract: This paper presents a pattern language based on regular expressions that allows the introduction of variables that can be instantiated to portions of the path that matches the expression. The paper will define a simple syntax for the language and its formal semantics. It will also study a modification of finite state automata that, through the introduction of actions on transitions, allows the variables to be instantiated while matching the expression. Finally, the paper will show that the problem of answering queries with variables is inherently harder than simple matching, essentially because, even for fairly simple expressions, the size of the results can be exponential in the size of the graph. The class of expressions and a class of graphs for which query answering is polynomial will be identified, and a processing algorithm for these expressions based on the intersection graph will be provided and analyzed. [Copyright &y& Elsevier]

Abstract: In this paper, we will present a generalization for a minimization problem from I. Daubechies, M. Defrise, and C. DeMol (2004) . This generalization is useful for solving many practical problems in which more than one constraint are involved. In this regard, we will conclude the findings of many papers (most of which are on image processing) from this generalization. It is hoped that the approach proposed in this paper will be a suitable reference for some applied works where multi-frames, multi-wavelets, or multi-constraints are present in linear inverse problems. [Copyright &y& Elsevier]

Abstract: “Clarithmetic” is a generic name for formal number theories similar to Peano arithmetic, but based on computability logic instead of the more traditional classical or intuitionistic logics. Formulas of clarithmetical theories represent interactive computational problems, and their “truth” is understood as existence of an algorithmic solution. Imposing various complexity constraints on such solutions yields various versions of clarithmetic. The present paper introduces a system of clarithmetic for polynomial time computability, which is shown to be sound and complete. Sound in the sense that every theorem T of the system represents an interactive number-theoretic computational problem with a polynomial time solution and, furthermore, such a solution can be efficiently extracted from a proof of T. And complete in the sense that every interactive number-theoretic problem with a polynomial time solution is represented by some theorem T of the system. The paper is written in a semitutorial style and targets readers with no prior familiarity with computability logic. [Copyright &y& Elsevier]

• Design temporal splitting together with multiscale methods to reduce the computational cost. • Study temporal splitting and spatial multiscale decomposition to extract implicit and explicit modes. • Use of GMsFEM within temporal splitting methods appropriately. In this paper, we study temporal splitting algorithms for multiscale problems. The exact fine-grid spatial problems typically require some reduction in degrees of freedom. Multiscale algorithms are designed to represent the fine-scale details on a coarse grid and, thus, reduce the problems' size. When solving time-dependent problems, one can take advantage of the multiscale decomposition of the solution and perform temporal splitting by solving smaller-dimensional problems, which is studied in the paper. In the proposed approach, we consider the temporal splitting based on various low dimensional spatial approximations. Because a multiscale spatial splitting gives a "good" decomposition of the solution space, one can achieve an efficient implicit-explicit temporal discretization. We present a recently developed theoretical result in [15] and adopt in this paper for multiscale problems. Numerical results are presented to demonstrate the efficiency of the proposed splitting algorithm. [ABSTRACT FROM AUTHOR]

Matrix completion involves recovering a matrix from a subset of its entries by utilizing interdependency between the entries, typically through low rank structure. Despite matrix completion requiring the global solution of a non-convex objective, there are many computationally efficient algorithms which are effective for a broad class of matrices. In this paper, we introduce an alternating steepest descent algorithm (ASD) and a scaled variant, ScaledASD, for the fixed-rank matrix completion problem. Empirical evaluation of ASD and ScaledASD on both image inpainting and random problems show they are competitive with other state-of-the-art matrix completion algorithms in terms of recoverable rank and overall computational time. In particular, their low per iteration computational complexity makes ASD and ScaledASD efficient for large size problems, especially when computing the solutions to moderate accuracy such as in the presence of model misfit, noise, and/or as an initialization strategy for higher order methods. A preliminary convergence analysis is also presented. [ABSTRACT FROM AUTHOR]

In this paper we analyze and extend mesh-free algorithms for three-dimensional data transfer problems in partitioned multiphysics simulations. We first provide a direct comparison between a mesh-based weighted residual method using the common-refinement scheme and two mesh-free algorithms leveraging compactly supported radial basis functions: one using a spline interpolation and one using a moving least square reconstruction. Through the comparison we assess both the conservation and accuracy of the data transfer obtained from each of the methods. We do so for a varying set of geometries with and without curvature and sharp features and for functions with and without smoothness and with varying gradients. Our results show that the mesh-based and mesh-free algorithms are complementary with cases where each was demonstrated to perform better than the other. We then focus on the mesh-free methods by developing a set of algorithms to parallelize them based on sparse linear algebra techniques. This includes a discussion of fast parallel radius searching in point clouds and restructuring the interpolation algorithms to leverage data structures and linear algebra services designed for large distributed computing environments. The scalability of our new algorithms is demonstrated on a leadership class computing facility using a set of basic scaling studies. These scaling studies show that for problems with reasonable load balance, our new algorithms for both spline interpolation and moving least square reconstruction demonstrate both strong and weak scalability using more than 100,000 MPI processes with billions of degrees of freedom in the data transfer operation. [ABSTRACT FROM AUTHOR]

Positive semidefiniteness, recursiveness, and the variety condition of a moment matrix are necessary and sufficient conditions to solve the quadratic and quartic moment problems. Also, positive semidefiniteness, combined with another necessary condition, consistency, is a sufficient condition in the case of extremal moment problems, i.e., when the rank of the moment matrix (denoted by r ) and the cardinality of the associated algebraic variety (denoted by v ) are equal. However, these conditions are not sufficient for non-extremal sextic or higher-order truncated moment problems. In this paper we settle three key instances of the non -extremal (i.e., r < v ) sextic moment problem, as follows: when r = 7 , positive semidefiniteness, consistency and the variety condition guarantee the existence of a 7-atomic representing measure; when r = 8 we construct two determining algorithms, corresponding to the cases v = 9 and v = + ∞ . To accomplish this, we generalize the rank-reduction technique developed in previous work, where we solved the nonsingular quartic moment problem and found an explicit way to build a representing measure. [ABSTRACT FROM AUTHOR]

Shooting methods are a well established tool for the numerical solution of terminal value problems of fractional order. However, they can be computationally quite expensive because of their iterative nature in which (a) each single iteration may be costly, and (b) the number of iterations can be large. In this paper we propose algorithmic strategies for improving the efficiency of such methods. Our strategies are aimed at simultaneously reducing the cost of each iteration and reducing the number of required iterations. [ABSTRACT FROM AUTHOR]

This paper describes an efficient implementation of triplet-based measures of stability, in the program TNT. The only available implementations of such measures are much slower than the present one, either because of an inefficient implementation (Phyutility, Thor) or because the stability is evaluated with quartets (RogueNaRok, requiring O ( t 4 ), instead of the O ( t 3 ) possible for triplets). The method to quickly calculate triplets is applied to solving IterPCR (Pol and Escapa, 2009). It is shown that, in some cases, IterPCR or other algorithms in the program TNT (e.g. commands prunnelsen , prunmajor , or chkmoves ) produce more informative results than analysis with RogueNaRok. [ABSTRACT FROM AUTHOR]

We study the problem of determining whether an n -node graph G contains an even hole , i.e., an induced simple cycle consisting of an even number of nodes. Conforti, Cornuéjols, Kapoor, and Vušković gave the first polynomial-time algorithm for the problem, which runs in O ( n 40 ) time. Later, Chudnovsky, Kawarabayashi, and Seymour reduced the running time to O ( n 31 ) . The best previously known algorithm for the problem, due to da Silva and Vušković, runs in O ( n 19 ) time. In this paper, we solve the problem in O ( n 11 ) time via a decomposition-based algorithm that relies on the decomposition theorem of da Silva and Vušković. Moreover, if G contains even holes, then our algorithm also outputs an even hole of G in O ( n 11 ) time. [ABSTRACT FROM AUTHOR]

Let H be a k -graph on n vertices, with minimum codegree at least n / k + c n for some fixed c > 0 . In this paper we construct a polynomial-time algorithm which finds either a perfect matching in H or a certificate that none exists. This essentially solves a problem of Karpiński, Ruciński and Szymańska; Szymańska previously showed that this problem is NP-hard for a minimum codegree of n / k − c n . Our algorithm relies on a theoretical result of independent interest, in which we characterise any such hypergraph with no perfect matching using a family of lattice-based constructions. [ABSTRACT FROM AUTHOR]

Algorithms to decide isomorphism of modules have been honed continually over the last 30 years, and their range of applicability has been extended to include modules over a wide range of rings. Highly efficient computer implementations of these algorithms form the bedrock of systems such as GAP and Magma , at least in regard to computations with groups and algebras. By contrast, the fundamental problem of testing for isomorphism between other types of algebraic structures – such as groups, and almost any type of algebra – seems today as intractable as ever. What explains the vastly different complexity status of the module isomorphism problem? This paper argues that the apparent discrepancy is explained by nomenclature. Current algorithms to solve module isomorphism, while efficient and immensely useful, are actually solving a highly constrained version of the problem. We report that module isomorphism in its general form is as hard as algebra isomorphism and graph isomorphism, both well-studied problems that are widely regarded as difficult. On a more positive note, for cyclic rings we describe a polynomial-time algorithm for the general module isomorphism problem. We also report on a Magma implementation of our algorithm. [ABSTRACT FROM AUTHOR]

Abstract: Minimum Fill-in is a fundamental and classical problem arising in sparse matrix computations. In terms of graphs it can be formulated as a problem of finding a triangulation of a given graph with the minimum number of edges. In this paper, we study the parameterized complexity of local search for the Minimum Fill-in problem in the following form: Given a triangulation H of a graph G, is there a better triangulation, i.e. triangulation with less edges than H, within a given distance from H? We prove that this problem is fixed-parameter tractable (FPT) being parameterized by the distance from the initial triangulation, by providing an algorithm that in time decides if a better triangulation of G can be obtained by swapping at most k edges of H. Our result adds Minimum Fill-in to the list of very few problems for which local search is known to be FPT. [Copyright &y& Elsevier]

In this paper, some numerical algorithms (spectral collocation method, block spectral collocation method, boundary value method, block boundary value method, implicit Runge–Kutta method, diagonally implicit Runge–Kutta method and total variation diminishing Runge–Kutta method) are used to solve the highly oscillatory second-order initial value problems. We first derive these methods for the first-order initial value problems, and then extend these methods to the highly oscillatory nonlinear systems by matrix analysis methods. These new methods preserve the accuracy of the original methods and the main advantages of these new methods are low storage requirements and high efficiency. Extensive numerical results are presented to demonstrate the convergence properties of these methods. [ABSTRACT FROM AUTHOR]

Linear Regression Classification (LRC) is a newly-appeared pattern recognition method, which formulates the recognition problem in terms of class-specific linear regression with sufficient training samples per class. In this paper, we extend LRC via intraclass variant dictionary and SVD to undersampled face recognition where there are very few, or even only one, training sample per class. Intraclass variant dictionary is adopted in undersampled situation to represent the possible variation between the training and testing samples. Three types of methods, quasi-inverse, ridge regularization and Singular Value Decomposition (SVD), are designed to solve low-rank problem of data matrix. Then the whole algorithm, named Extended LRC (ELRC), is presented for face recognition via intraclass variant dictionary and SVD. The experimental results on three well-known face databases show that the proposed ELRC has better generalization ability and is more robust to classification than many state-of-the-art methods in undersampled situation. [ABSTRACT FROM AUTHOR]

In this paper, we propose a stereo matching algorithm based on distance transform to generate high-quality disparity maps with occlusion handling. In general, pixel intensities around object edges are smeared due to mixed values located between the object and its background. This leads to problems when identifying discontinuous disparities. In order to handle these problems, we present an edge control function according to distance transform values. Meanwhile, occluded regions occur, i.e., some portions are visible only in one image. An energy function is designed to detect such regions considering warping, cross check, and luminance difference constraints. Consequently, we replace the disparity in the occluded region with the one chosen from its neighboring disparities in the non-occluded region based on color and spatial correlations. In particular, the occlusion hole is filled according to region types. Experimental results show that the proposed method outperforms conventional stereo matching algorithms with occlusion handling. [ABSTRACT FROM AUTHOR]

In this paper we consider the numerical solution of the three-dimensional fluid-structure interaction problem in haemodynamics, in the case of real geometries, physiological data and finite elasticity vessel deformations. We study some new inexact schemes, obtained from semi-implicit approximations, which treat exactly the physical interface conditions while performing just one or few iterations for the management of the interface position and of the fluid and structure non-linearities. We show that such schemes allow to improve the efficiency while preserving the accuracy of the related exact (implicit) scheme. To do this we consider both a simple analytical test case and two real cases of clinical interest in haemodynamics. We also provide an error analysis for a simple differential model problem when a BDF method is considered for the time discretization and only few Newton iterations are performed at each temporal instant. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we present a simple and efficient computational algorithm for solving eigenvalue problems of high fractional-order differential equations with variable coefficients. The method of solution is based on utilizing the series solution to convert the governing fractional differential equation into a linear system of algebraic equations. Then, the eigenvalues can be calculated by finding the roots of the corresponding characteristic polynomial. Notice that this class of eigenvalue problems is very promising to the solution of linear fractional partial differential equations (FPDE). The numerical results demonstrate reliability and efficiency of the proposed algorithm. Based on our simulations some theoretical conjectures are reported. [Copyright &y& Elsevier]

Abstract: In a number of problems in computational physics, a finite sum of kernel functions centered at N particle locations located in a box in three dimensions must be extended by imposing periodic boundary conditions on box boundaries. Even though the finite sum can be efficiently computed via fast summation algorithms, such as the fast multipole method (FMM), the periodized extension is usually treated via a different algorithm, Ewald summation, accelerated via the fast Fourier transform (FFT). A different approach to compute this periodized sum just using a blackbox finite fast summation algorithm is presented in this paper. The method splits the periodized sum into two parts. The first, comprising the contribution of all points outside a large sphere enclosing the box, and some of its neighbors, is approximated inside the box by a collection of kernel functions (“sources”) placed on the surface of the sphere or using an expansion in terms of spectrally convergent local basis functions. The second part, comprising the part inside the sphere, and including the box and its immediate neighborhood, is treated via available summation algorithms. The coefficients of the sources are determined by least squares collocation of the periodicity condition of the total potential, imposed on a circumspherical surface for the box. While the method is presented in general, details are worked out for the case of evaluating electrostatic potentials and forces. Results show that when used with the FMM, the periodized sum can be computed to any specified accuracy, at an additional cost of the order of the free-space FMM. Several technical details and efficient algorithms for auxiliary computations are provided, as are numerical comparisons. [Copyright &y& Elsevier]

Abstract: There are a number of modeling challenges posed by space weather simulations. Most of them arise from the multiscale and multiphysics aspects of the problem. The multiple scales dramatically increase the requirements, in terms of computational resources, because of the need of performing large scale simulations with the proper small-scales resolution. Lately, several suggestions have been made to overcome this difficulty by using various refinement methods which consist in splitting the domain into regions of different resolutions separated by well defined interfaces. The multiphysics issues are generally treated in a similar way: interfaces separate the regions where different equations are solved. This paper presents an innovative approach based on the coexistence of several levels of description, which differ by their resolutions or, potentially, by their physics. Instead of interacting through interfaces, these levels are entirely simulated and are interlocked over the complete extension of the overlap area. This scheme has been applied to a parallelized, two-dimensional, Implicit Moment Method Particle in Cell code in order to investigate its multiscale description capabilities. Simulations of magnetic reconnection and plasma expansion in vacuum are presented and possible implementation options for this scheme on very large systems are also discussed. [Copyright &y& Elsevier]

Abstract: Permutation methods can provide exact control of false positives and allow the use of non-standard statistics, making only weak assumptions about the data. With the availability of fast and inexpensive computing, their main limitation would be some lack of flexibility to work with arbitrary experimental designs. In this paper we report on results on approximate permutation methods that are more flexible with respect to the experimental design and nuisance variables, and conduct detailed simulations to identify the best method for settings that are typical for imaging research scenarios. We present a generic framework for permutation inference for complex general linear models (glms) when the errors are exchangeable and/or have a symmetric distribution, and show that, even in the presence of nuisance effects, these permutation inferences are powerful while providing excellent control of false positives in a wide range of common and relevant imaging research scenarios. We also demonstrate how the inference on glm parameters, originally intended for independent data, can be used in certain special but useful cases in which independence is violated. Detailed examples of common neuroimaging applications are provided, as well as a complete algorithm – the “randomise” algorithm – for permutation inference with the glm. [Copyright &y& Elsevier]

Abstract: In this paper, based on differential characteristic set theory and the associated algorithm (also called Wuʼs method), an algorithmic method is presented to decide on the existence of a nontrivial non-classical symmetry of a given partial differential equation without solving the corresponding nonlinear determining system. The theory and algorithm give a partial answer for the open problem posed by P.A. Clarkson and E.L. Mansfield in [21] on non-classical symmetries of partial differential equations. As applications of our algorithm, non-classical symmetries and corresponding invariant solutions are found for several evolution equations. [Copyright &y& Elsevier]

Abstract: In this paper we present a fast and high-order boundary integral equation method for the elastic scattering by three-dimensional large penetrable obstacles. The algorithm extends the method introduced in [5] for the acoustic surface scattering to the fully elastic case. In our algorithm, high-order accuracy is achieved through the use of the partition of unity and a semi-classical treatment of relevant singular integrals. The computational efficiency associated with the nonsingular integrals is attained by the method of equivalent source representations on a Cartesian grid and Fast Fourier Transform (FFT). The resulting algorithm computes one matrix–vector product associated with the discretization of the integral equation with operations, and it shows algebraic convergence. Several numerical experiments are provided to demonstrate the efficiency of the method. [Copyright &y& Elsevier]

Abstract: In this paper, a novel local mesh refinement algorithm based on transformation optics (TO) has been developed for solving the Maxwellʼs equations of electrodynamics. The new algorithm applies transformation optics to enlarge a small region so that it can be resolved by larger grid cells. The transformed anisotropic Maxwellʼs equations can be stably solved by an anisotropic FDTD method, while other subgridding or adaptive mesh refinement FDTD methods require time–space field interpolations and often suffer from the late-time instability problem. To avoid small time steps introduced by the transformation optics approach, an additional application of the mapping of the material matrix to a dispersive material model is employed. Numerical examples on scattering problems of dielectric and dispersive objects illustrate the performance and the efficiency of the transformation optics based FDTD method. [Copyright &y& Elsevier]

Abstract: In this paper, a class of general nonlinear programming problems with inequality and equality constraints is discussed. Firstly, the original problem is transformed into an associated simpler equivalent problem with only inequality constraints. Then, inspired by the ideals of the sequential quadratic programming (SQP) method and the method of system of linear equations (SLE), a new type of SQP algorithm for solving the original problem is proposed. At each iteration, the search direction is generated by the combination of two directions, which are obtained by solving an always feasible quadratic programming (QP) subproblem and a SLE, respectively. Moreover, in order to overcome the Maratos effect, the higher-order correction direction is obtained by solving another SLE. The two SLEs have the same coefficient matrices, and we only need to solve the one of them after a finite number of iterations. By a new line search technique, the proposed algorithm possesses global and superlinear convergence under some suitable assumptions without the strict complementarity. Finally, some comparative numerical results are reported to show that the proposed algorithm is effective and promising. [Copyright &y& Elsevier]

CG_DESCENT is a state-of-the-art algorithm to solve large-scale unconstrained minimization problems. However, research activities on CG_DESCENT in some other scenarios are relatively fewer. In this paper, by combining with the projection method of Solodov and Svaiter, we extend CG_DESCENT to solve large-scale nonlinear convex constrained monotone equations. The proposed method does not require the Jacobian information, even though it does not store any matrix at each iteration. It thus has the potential to solve large-scale non-smooth problems. Under some mild conditions, we show that the proposed method converges globally. Primary numerical results illustrate that the proposed method works quite well. Moreover, we also extend this method to solve the -norm regularized problems to decode a sparse signal in compressive sensing. Performance comparisons show that the proposed method is practical, efficient and competitive with the compared ones. [ABSTRACT FROM AUTHOR]

• MEMS-INS, GPS and polarization compass are integrated together for navigation. • A multi-rate algorithm is proposed to solve the problem caused by different sampling frequencies. • Singular value decomposition is used to improve the numerical stability of the algorithm. The microelectromechanical system-inertial navigation system (MEMS-INS) is one of the most widely used sensor systems in navigation but must be used with other sensors because of its error accumulation characteristics. The information fusion method for integrated navigation systems based on filtering technology is thus very important. This paper introduces a new adaptive Kalman filter for nonlinear integrated systems. An improved multi-rate strong tracking square-root cubature Kalman filter (MR-STSCKF) for a MEMS-INS/Global Positioning System (GPS)/polarization compass integrated navigation system is proposed. The proposed filter is used to estimate the system covariance adaptively. The proposed approach can overcome the problem of the inconsistency between the sampling frequencies of different sensors while maintaining the high precision of the integrated navigation results. Experimental results demonstrate that the proposed MR-STSCKF algorithm is effective in improving the accuracy of the MEMS-INS/GPS/polarization compass integrated navigation system with a high sampling frequency. [ABSTRACT FROM AUTHOR]

Branching Algebra is the natural branching-time generalization of Allen's Interval Algebra. As in the linear case, the consistency problem for Branching Algebra is NP-hard. Branching Algebra has many potential applications in different areas of Artificial Intelligence; therefore, being able to efficiently solve classical problems expressed in Branching Algebra is very important. This can be achieved in two steps: first, by identifying expressive enough, yet tractable fragments of the whole algebra, and, second, by using such fragments to boost the performances of a backtracking algorithm for the whole language. In this paper we study the properties of several such fragments, both from the algebraic and the computational point of view, and we give an almost complete picture of tractable and non-tractable fragments of the Branching Algebra. [ABSTRACT FROM AUTHOR]

Simon's problem plays an important role in the history of quantum algorithms, as it inspired Shor to discover the celebrated quantum algorithm solving integer factorization in polynomial time. Besides, the quantum algorithm for Simon's problem has been recently applied to break symmetric cryptosystems. Generalized Simon's problem, denoted by GSP (p , n , k) , is a natural extension of Simon's problem: Given a function f : Z p n → X where X is a finite set and the promise that for any x , y ∈ Z p n , f (x) = f (y) iff x − y ∈ S for a subgroup S ≤ Z p n of rank k < n , the goal is to find S. In this paper we consider the query complexity of the problem, that is, the minimum number of queries to f required to find S. First, it is not difficult to design a quantum algorithm solving the above problem with query complexity of O (n − k). However, so far it is not clear what is the classical query complexity of the problem, and revealing this complexity is necessary for clarifying the computational power gap between quantum and classical computing on the problem. To tackle this problem, we prove that any classical (deterministic or randomized) algorithm for GSP (p , n , k) has to query at least Ω (max ⁡ { k , p n − k }) values and any classical nonadaptive deterministic algorithm for GSP (p , n , k) has to query at least Ω (max ⁡ { k , k ⋅ p n − k }) values. Hence, we clearly show the classical computing model is less powerful than the quantum counterpart, in terms of query complexity for the generalized Simon's problem. Moreover, we obtain an upper bound O (max ⁡ { k , k ⋅ p n − k }) on the classical deterministic query complexity of GSP (p , n , k) , by devising a subtle classical algorithm based on group theory and the divide-and-conquer approach. Therefore, we have an almost full characterization of the classical deterministic query complexity of the generalized Simon's problem. [ABSTRACT FROM AUTHOR]

Abstract: This paper studies the risk probability criteria for finite horizon semi-Markov decision processes. The goal is to find an optimal policy with the minimum risk probability that the total reward produced by a system during a finite horizon does not exceed a reward level, where the optimality is over the class of all randomized historic policies which include states, planning horizons and also reward levels. Under mild conditions, the optimality equation and the existence of optimal policies are established, and in addition, an iteration algorithm for solving optimal policies is developed. Our main results are applied to a manufacturing system. [Copyright &y& Elsevier]

Abstract: In this paper we present a technique for shape reconstruction based on the topological and shape gradients. The shape in consideration is a solution of an inverse conductivity problem. To solve such a problem numerically, we compute the topological gradient of a Kohn–Vogelius-type cost function when the domain under consideration is perturbed by the introduction of a small inclusion instead of a hole. The reconstruction is done by considering the shape as a superposition of very thin elliptic inclusions to get a first approximation. Then, we use a gradient-type algorithm to perform a good reconstruction. Various numerical experiments of single and multiple inclusions demonstrate the viability of the designed algorithm. [Copyright &y& Elsevier]

Abstract: In this paper we develop new algorithmic machinery for solving hard problems on graphs of bounded rank-width and on digraphs of bounded bi-rank-width in polynomial (XP, to be precise) time. These include, particularly, graph coloring and chromatic polynomial problems, the Hamiltonian path and -min-leaf outbranching, the directed cut, and more generally MSOL-partitioning problems on digraphs. Our focus on a formally clean and unified approach for the considered algorithmic problems is in contrast with many previous published XP algorithms running on graphs of bounded clique-width, which mostly used ad hoc techniques and ideas. The new contributions include faster algorithms for computing the chromatic number and the chromatic polynomial on graphs of bounded rank-width, and new algorithms for solving the defective coloring, the min-leaf outbranching, and the directed cut problems. [Copyright &y& Elsevier]

Abstract: After a decade of extensive study of the sparse representation synthesis model, we can safely say that this is a mature and stable field, with clear theoretical foundations, and appealing applications. Alongside this approach, there is an analysis counterpart model, which, despite its similarity to the synthesis alternative, is markedly different. Surprisingly, the analysis model did not get a similar attention, and its understanding today is shallow and partial. In this paper we take a closer look at the analysis approach, better define it as a generative model for signals, and contrast it with the synthesis one. This work proposes effective pursuit methods that aim to solve inverse problems regularized with the analysis-model prior, accompanied by a preliminary theoretical study of their performance. We demonstrate the effectiveness of the analysis model in several experiments, and provide a detailed study of the model associated with the 2D finite difference analysis operator, a close cousin of the TV norm. [Copyright &y& Elsevier]

Abstract: Survivability is one of the key issues in Fiber-Wireless (FiWi) access network because network component failures may cause huge data loss, especially when the failures in optical back-end. According to the failure severity, we categorize the failures in optical back-end into two levels, that is, Optical-Network-Unit (ONU)-level failure and segment-level failure. In this paper, instead of the expensive fiber duplication approach traditionally, we propose a novel protection approach for FiWi against ONU-level failure by assigning each ONU several alternate ONUs in the same segment and against the segment-level failure by deploying backup fibers among different segments. On one hand, we optimize the assignment of alternate ONUs, aiming to maximize the amount of protected traffic and minimize the number of wireless hops. On the other hand, we optimize the deployment of backup fibers, aiming to maximize the amount of protected traffic and minimize the length of backup fibers. We mathematically formulate these two objectives as Maximum Protection and Minimum Hops Number (MPMHN) problem and the Maximum Protection and Minimum backup Fibers Length (MPMFL) problem, respectively. An efficient algorithm called Auxiliary Graph based Protection (AGP) is proposed to solve the MPMHN and MPMFL problems. In the simulation, we investigate the performance of AGP in various scenarios and demonstrate the cost-efficiency of the proposed protection approach. [Copyright &y& Elsevier]

Abstract: With the advent of new sequencing technologies able to produce an enormous quantity of short genomic sequences, new tools able to search for them inside a genomic reference sequence have emerged. Because of chemical reading errors or of the variability between organisms, one is interested in finding not only exact occurrences, but also occurrences with up to k mismatches. The contribution of this paper is twofold. On the one hand, we present a generalization of the classical Rabin–Karp string matching algorithm to solve the k-mismatch problem, with average complexity (n text and m pattern lengths, respectively). On the other hand, we show how to employ this idea in conjunction with an index over the text, allowing to search a pattern, with up to k mismatches, in time proportional to its length. This novel tool—rNA (randomized Numerical Aligner)—is in general faster and more accurate than other available tools like SOAP2, BWA, and BOWTIE. rNA executables and source code are freely available at http://iga-rna.sourceforge.net/ . [Copyright &y& Elsevier]

Abstract: Unstructured meshes are in widespread use throughout computational physics, but calculating diagnostics of simulations on such meshes can be challenging. For example, in geophysical fluid dynamics, it is frequently desirable to compute directional integrals such as vertical integrals and zonal averages; however, it is difficult to compute these on meshes with no inherent spatial structure. This is widely regarded as an obstacle to the adoption of unstructured mesh numerical modelling in this field. In this paper, we describe an algorithm by which one can exactly compute such directional integrals on arbitrarily unstructured meshes. This is achieved via the solution of a problem of computational geometry, constructing the supermesh of two meshes. We demonstrate the utility of this approach by applying it to a classical geophysical fluid dynamics system: the thermally driven rotating annulus. This addresses an important objection to the more widespread use of unstructured mesh modelling. [Copyright &y& Elsevier]

Abstract: In this paper, we study a design method for minimizing the total cost of a wireless sensor network (WSN) used for health monitoring of railway structures. First, we present the problem, that is to simultaneously determine the number of relays and their deployment locations, the transmission power level for each sensor and relay, and the routes for transferring sensor data to a gateway using multi-hop wireless communication. Second, we formulate this task as a mathematical programming problem, and to solve this problem, we propose a near optimal algorithm based on the Lagrangian heuristic method. Finally, we verify the effectiveness of our algorithm through computational experiments carried out using data acquired from a real WSN used for railway structural health monitoring. [Copyright &y& Elsevier]

Abstract: Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. One fast computational haplotyping method is based on an evolutionary model where a perfect phylogenetic tree is sought that explains the observed data. An extension of this approach tries to incorporate prior knowledge in the form of a set of candidate haplotypes from which the right haplotypes must be chosen. The objective is to increase the accuracy of haplotyping methods, but it was conjectured that the resulting formal problem constrained perfect phylogeny haplotyping might be NP-complete. In the paper at hand we present a polynomial-time algorithm for it. Our algorithmic ideas also yield new fixed-parameter algorithms for related haplotyping problems based on the maximum parsimony assumption. [Copyright &y& Elsevier]