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]

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]

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]

Few-shot learning aims to recognize instances from novel classes with few labeled samples, which has great value in research and application. Although there has been a lot of work in this area recently, most of the existing work is based on image classification tasks. Video-based few-shot action recognition has not been explored well and remains challenging: (1) the differences of implementation details among different papers make a fair comparison difficult; (2) the wide variations and misalignment of temporal sequences make the video-level similarity comparison difficult; (3) the scarcity of labeled data makes the optimization difficult. To solve these problems, this paper presents (1) a specific setting to evaluate the performance of few-shot action recognition algorithms; (2) an implicit sequence-alignment algorithm for better video-level similarity comparison; (3) an advanced loss for few-shot learning to optimize pair similarity with limited data. Specifically, we propose a novel few-shot action recognition framework that uses long short-term memory following 3D convolutional layers for sequence modeling and alignment. Circle loss is introduced to maximize the within-class similarity and minimize the between-class similarity flexibly towards a more definite convergence target. Instead of using random or ambiguous experimental settings, we set a concrete criterion analogous to the standard image-based few-shot learning setting for few-shot action recognition evaluation. Extensive experiments on two datasets demonstrate the effectiveness of our proposed method. • A novel implicit sequence-alignment algorithm to calculate the similarity between videos. • Pair-wise similarities are re-weighted flexibly during training according to their status. • A specific and standard experimental setting is clearly defined. • Extensive experiments demonstrate the effectiveness and superiority of the proposed model. [ABSTRACT FROM AUTHOR]

• 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]

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]

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]

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]

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]

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]

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]

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]

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]

• 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]

• We present the SSLE approach for Bayesian model inversion based on SSE and SLE. • Posterior quantities are obtained analytically from the SSLE coefficients. • The original SSE algorithm is enhanced with an active learning enrichment scheme. • This method generalizes and drastically improves the efficiency of the SLE approach. • We showcase the method on three problems of different complexity and dimensionality. In this paper we propose a new sampling-free approach to solve Bayesian model inversion problems that is an extension of the previously proposed spectral likelihood expansions (SLE) method. Our approach, called stochastic spectral likelihood embedding (SSLE), uses the recently presented stochastic spectral embedding (SSE) method for local spectral expansion refinement to approximate the likelihood function at the core of Bayesian inversion problems. We show that, similar to SLE, this approach results in analytical expressions for key statistics of the Bayesian posterior distribution, such as evidence, posterior moments and posterior marginals , by direct post-processing of the expansion coefficients. Because SSLE and SSE rely on the direct approximation of the likelihood function, they are in a way independent of the computational/mathematical complexity of the forward model. We further enhance the efficiency of SSLE by introducing a likelihood specific adaptive sample enrichment scheme. To showcase the performance of the proposed SSLE, we solve three problems that exhibit different kinds of complexity in the likelihood function: multimodality, high posterior concentration and high nominal dimensionality. We demonstrate how SSLE significantly improves on SLE, and present it as a promising alternative to existing inversion frameworks. [ABSTRACT FROM AUTHOR]

This paper proposes a new methodology for modelling chronological data in archaeology. We introduce the concept of "chronological network", a flexible model for representing chronological entities, synchronisms between them, and other chronological constraints such as termini post/ante quem and duration bounds. We propose a procedure for checking the consistency of a chronological network and for refining dating estimates from the available synchronisms and constraints. We introduce ChronoLog, a chronology software application that allows users to build a chronological network interactively. The software automatically checks the consistency of the network and computes the tightest possible chronological range for each entity, within seconds. ChronoLog is freely available online at http://chrono.ulb.be. • We present a new conceptual model of chronological networks in archaeology. • We present a mathematical formalisation of chronological networks in archaeology. • We propose algorithms for solving chronological problems in archaeology. • We propose new software for modelling chronological networks. • We propose a case study related to the Egyptian 26th dynasty. [ABSTRACT FROM AUTHOR]