A low level component model easing performance portability of HPC applications

Scientific applications are getting increasingly complex, e.g., to improve their accuracy by taking into account more phenomena. Meanwhile, computing infrastructures are continuing their fast evolution. Thus, software engineering is becoming a major issue to offer ease of development, portability and maintainability while achieving high performance. Component based software engineering offers a promising approach that enables the manipulation of the software architecture of applications. However, existing models do not provide an adequate support for performance portability of HPC applications. This paper proposes a low level component model (L \(^2\) C) that supports inter-component interactions for typical scenarios of high performance computing, such as process-local shared memory and function invocation (C++ and Fortran), MPI, and Corba. To study the benefits of using L \(^2\) C, this paper walks through an example of stencil computation, i.e. a structured mesh Jacobi implementation of the 2D heat equation parallelized through domain decomposition. The experimental results obtained on the Grid’5000 testbed and on the Curie supercomputer show that L \(^2\) C can achieve performance similar to that of native implementations, while easing performance portability.     

Query reverse engineering

In this paper, we introduce a new problem termed query reverse engineering (QRE). Given a database \(D\) and a result table \(T\) —the output of some known or unknown query \(Q\) on \(D\) —the goal of QRE is to reverse-engineer a query \(Q'\) such that the output of query \(Q'\) on database \(D\) (denoted by \(Q'(D)\) ) is equal to \(T\) (i.e., \(Q(D)\) ). The QRE problem has useful applications in database usability, data analysis, and data security. In this work, we propose a data-driven approach, TALOS for Tree-based classifier with At Least One Semantics, that is based on a novel dynamic data classification formulation and extend the approach to efficiently support the three key dimensions of the QRE problem: whether the input query is known/unknown, supporting different query fragments, and supporting multiple database versions.     

A C^0-Weak Galerkin Finite Element Method for the Biharmonic Equation

A $C^0$ -weak Galerkin (WG) method is introduced and analyzed in this article for solving the biharmonic equation in 2D and 3D. A discrete weak Laplacian is defined for $C^0$ functions, which is then used to design the weak Galerkin finite element scheme. This WG finite element formulation is symmetric, positive definite and parameter free. Optimal order error estimates are established for the weak Galerkin finite element solution in both a discrete $H^2$ norm and the standard $H^1$ and $L^2$ norms with appropriate regularity assumptions. Numerical results are presented to confirm the theory. As a technical tool, a refined Scott-Zhang interpolation operator is constructed to assist the corresponding error estimates. This refined interpolation preserves the volume mass of order $(k+1-d)$ and the surface mass of order $(k+2-d)$ for the $P_{k+2}$ finite element functions in $d$ -dimensional space.     

Solving Convection-Diffusion Problems on Curved Domains by Extensions from Subdomains

We present a technique for numerically solving convection-diffusion problems in domains $\varOmega $ with curved boundary. The technique consists in approximating the domain $\varOmega $ by polyhedral subdomains $\mathsf{{D}}_h$ where a finite element method is used to solve for the approximate solution. The approximation is then suitably extended to the remaining part of the domain $\varOmega $ . This approach allows for the use of only polyhedral elements; there is no need of fitting the boundary in order to obtain an accurate approximation of the solution. To achieve this, the boundary condition on the border of $\varOmega $ is transferred to the border of $\mathsf{D }_h$ by using simple line integrals. We apply this technique to the hybridizable discontinuous Galerkin method and provide extensive numerical experiments showing that, whenever the distance of $\mathsf{{D}}_h$ to $\partial \varOmega $ is of order of the meshsize $h$ , the convergence properties of the resulting method are the same as those for the case in which $\varOmega =\mathsf{{D}}_h$ . We also show numerical evidence indicating that the ratio of the $L^2(\varOmega )$ norm of the error in the scalar variable computed with $d>0$ to that of that computed with $d=0$ remains constant (and fairly close to one), whenever the distance $d$ is proportional to $\min \{h,Pe^{-1}\}/(k+1)^2$ , where $Pe$ is the so-called Péclet number.     

Robust sparsity-preserved learning with application to image visualization

Linear subspace learning is of great importance for the purpose of visualization of high-dimensional observations. Sparsity-preserved learning (SPL) is a recently developed technique for linear subspace learning. Its objective function is formulated by using the $\ell _2$ -norm, which implies that the obtained projection vectors are likely to be distorted by outliers. In this paper, we develop a new SPL algorithm called SPL-L1 based on the $\ell _1$ -norm instead of the $\ell _2$ -norm. The proposed approach seeks projection vectors by minimizing a reconstruction error subject to a constraint of samples dispersion, both of which are defined using the $\ell _1$ -norm. As a robust alternative, SPL-L1 works well in the presence of atypical samples. We design an iterative algorithm under the framework of bound optimization to solve the projection vectors of SPL-L1. The experiments on image visualization demonstrate the superiority of the proposed method.     

Order optimal information spreading using algebraic gossip

In this paper we study gossip based information spreading with bounded message sizes. We use algebraic gossip to disseminate $k$ distinct messages to all $n$ nodes in a network. For arbitrary networks we provide a new upper bound for uniform algebraic gossip of $O((k+\log n + D)\varDelta )$ rounds with high probability, where $D$ and $\varDelta $ are the diameter and the maximum degree in the network, respectively. For many topologies and selections of $k$ this bound improves previous results, in particular, for graphs with a constant maximum degree it implies that uniform gossip is order optimal and the stopping time is $\varTheta (k + D)$ . To eliminate the factor of $\varDelta $ from the upper bound we propose a non-uniform gossip protocol, TAG, which is based on algebraic gossip and an arbitrary spanning tree protocol $\mathcal{S } $ . The stopping time of TAG is $O(k+\log n +d(\mathcal{S })+t(\mathcal{S }))$ , where $t(\mathcal{S })$ is the stopping time of the spanning tree protocol, and $d(\mathcal{S })$ is the diameter of the spanning tree. We provide two general cases in which this bound leads to an order optimal protocol. The first is for $k=\varOmega (n)$ , where, using a simple gossip broadcast protocol that creates a spanning tree in at most linear time, we show that TAG finishes after $\varTheta (n)$ rounds for any graph. The second uses a sophisticated, recent gossip protocol to build a fast spanning tree on graphs with large weak conductance. In turn, this leads to the optimally of TAG on these graphs for $k=\varOmega (\text{ polylog }(n))$ . The technique used in our proofs relies on queuing theory, which is an interesting approach that can be useful in future gossip analysis.     

Tight Bounds for Distributed Minimum-Weight Spanning Tree Verification

This paper introduces the notion of distributed verification without preprocessing. It focuses on the Minimum-weight Spanning Tree (MST) verification problem and establishes tight upper and lower bounds for the time and message complexities of this problem. Specifically, we provide an MST verification algorithm that achieves simultaneously $\tilde{O}(m)$ messages and $\tilde{O}(\sqrt{n} + D)$ time, where m is the number of edges in the given graph G, n is the number of nodes, and D is G’s diameter. On the other hand, we show that any MST verification algorithm must send $\tilde{\varOmega}(m)$ messages and incur $\tilde{\varOmega}(\sqrt{n} + D)$ time in worst case. Our upper bound result appears to indicate that the verification of an MST may be easier than its construction, since for MST construction, both lower bounds of $\tilde{\varOmega}(m)$ messages and $\tilde{\varOmega}(\sqrt{n} + D)$ time hold, but at the moment there is no known distributed algorithm that constructs an MST and achieves simultaneously $\tilde{O}(m)$ messages and $\tilde{O}(\sqrt{n} + D)$ time. Specifically, the best known time-optimal algorithm (using ${\tilde{O}}(\sqrt {n} + D)$ time) requires O(m+n ^3/2) messages, and the best known message-optimal algorithm (using ${\tilde{O}}(m)$ messages) requires O(n) time. On the other hand, our lower bound results indicate that the verification of an MST is not significantly easier than its construction.     

An integrated GA-DEA algorithm for determining the most effective maintenance policy for a k -out-of- n problem

This paper presents a novel hybrid GA-DEA algorithm in order to solve multi-objective \(k\) -out-of- \(n\) problem and determine preferred policy. The proposed algorithm maximizes overall system reliability and availability, while minimizing system cost and queue length, simultaneously. To meet these objectives, an adaptive hybrid GA-DEA algorithm is developed to identify the optimal solutions and improve computation efficiency. In order to improve computation efficiency genetic algorithm (GA) is used to simulate a series production line and find the Pareto-optimal solutions which are different values of \(k\) and \(n\) of \(k\) -out-of- \(n\) problem. Data envelopment analysis is used to find the best \(k\) and \(n\) from Genetic Algorithm’s Pareto solutions. An illustrative example is applied to show the flexibility and effectiveness of the proposed algorithm. The proposed algorithm of this study would help managers to identify the preferred policy considering and investigating various parameters and scenarios in logical time. Also considering different objectives result in Pareto-optimal solutions that would help decision makers to select the preferred solution based on their situation and preference.     

pROST: a smoothed \ell _p-norm robust online subspace tracking method for background subtraction in video

An increasing number of methods for background subtraction use Robust PCA to identify sparse foreground objects. While many algorithms use the \(\ell _1\) -norm as a convex relaxation of the ideal sparsifying function, we approach the problem with a smoothed \(\ell _p\) -quasi-norm and present pROST, a method for robust online subspace tracking. The algorithm is based on alternating minimization on manifolds. Implemented on a graphics processing unit, it achieves realtime performance at a resolution of \(160 \times 120\) . Experimental results on a state-of-the-art benchmark for background subtraction on real-world video data indicate that the method succeeds at a broad variety of background subtraction scenarios, and it outperforms competing approaches when video quality is deteriorated by camera jitter.     

Efficient Fully-Compressed Sequence Representations

We present a data structure that stores a sequence s[1..n] over alphabet [1..σ] in $n\mathcal{H}_{0}(s) + o(n)(\mathcal {H}_{0}(s){+}1)$ bits, where $\mathcal{H}_{0}(s)$ is the zero-order entropy of s. This structure supports the queries access, rank and select, which are fundamental building blocks for many other compressed data structures, in worst-case time ${\mathcal{O} ( {\lg\lg\sigma} )}$ and average time ${\mathcal{O} ( {\lg\mathcal{H}_{0}(s)} )}$ . The worst-case complexity matches the best previous results, yet these had been achieved with data structures using $n\mathcal{H}_{0}(s)+o(n\lg \sigma)$ bits. On highly compressible sequences the o(nlgσ) bits of the redundancy may be significant compared to the $n\mathcal{H}_{0}(s)$ bits that encode the data. Our representation, instead, compresses the redundancy as well. Moreover, our average-case complexity is unprecedented. Our technique is based on partitioning the alphabet into characters of similar frequency. The subsequence corresponding to each group can then be encoded using fast uncompressed representations without harming the overall compression ratios, even in the redundancy. The result also improves upon the best current compressed representations of several other data structures. For example, we achieve (i) compressed redundancy, retaining the best time complexities, for the smallest existing full-text self-indexes; (ii) compressed permutations π with times for π() and π ^?1() improved to loglogarithmic; and (iii) the first compressed representation of dynamic collections of disjoint sets. We also point out various applications to inverted indexes, suffix arrays, binary relations, and data compressors. Our structure is practical on large alphabets. Our experiments show that, as predicted by theory, it dominates the space/time tradeoff map of all the sequence representations, both in synthetic and application scenarios.     

Finding large k-clubs in undirected graphs

Finding cohesive subgroups is an important issue in studying social networks. Many models exist for defining cohesive subgraphs in social networks, such as clique, $k$ -clique, and $k$ -clan. The concept of $k$ -club is one of them. A $k$ -club of a graph is a maximal subset of the vertex set which induces a subgraph of diameter $k$ . It is a relaxation of a clique, which induces a subgraph of diameter $1$ . We conducted algorithmic studies on finding a $k$ -club of size as large as possible. In this paper, we show that one can find a $k$ -club of maximum size in $O^{*}(1.62^n)$ time where $n$ is the number of vertices of the input graph. We implemented a combinatorial branch-and-bound algorithm that finds a $k$ -club of maximum size and a new heuristic algorithm called IDROP given in this paper. To speed up the programs, we introduce a dynamic data structure called $k$ -DN which, under deletion of vertices from a graph, maintains for a given vertex $v$ the set of vertices at distances at most $k$ . From the experimental results that we obtained, we concluded that a $k$ -club of maximum size can be easily found in sparse graphs and dense graphs. Our heuristic algorithm finds, within reasonable time, $k$ -clubs of maximum size in most of experimental instances. The gap between the size of a $k$ -club of maximum size and a $k$ -club found by IDROP is a constant for the number of vertices that we are able to test.     

Optimal quadrature formulas in the sense of Sard in W_2^{(m,m-1)} space

This paper studies the problem of construction of optimal quadrature formulas in the sense of Sard in the $W_2^{(m,m-1)}(0,1)$ space. Using the Sobolev’s method we obtain new optimal quadrature formulas of such type for $N+1\ge m$ , where $N+1$ is the number of the nodes. Moreover, explicit formulas of the optimal coefficients are obtained. We investigate the order of convergence of the optimal formula for $m=1$ and prove an asymptotic optimality of such a formula in the Sobolev space $L_2^{(1)}(0,1)$ . It turns out that the error of the optimal quadrature formula in $W_2^{(1,0)}(0,1)$ is less than the error of the optimal quadrature formula given in the $L_2^{(1)}(0,1)$ space. The obtained optimal quadrature formula in the $W_2^{(m,m-1)}(0,1)$ space is exact for $\exp (-x)$ and $P_{m-2}(x)$ , where $P_{m-2}(x)$ is a polynomial of degree $m-2$ . Furthermore, some numerical results, which confirm the obtained theoretical results of this work, are given.     

Deriving length two path centered surface area for the arrangement graph: a generating function approach

We discuss the notion of \(H\) -centered surface area of a graph \(G\) , where \(H\) is a subgraph of \(G\) , i.e., the number of vertices in \(G\) at a certain distance from \(H\) , and focus on the special case when \(H\) is a length two path to derive an explicit formula for the length two path centered surface area of the general and scalable arrangement graph, following a generating function approach.     

Optimized Parameter Search for Large Datasets of the Regularization Parameter and Feature Selection for Ridge Regression

In this paper we propose mathematical optimizations to select the optimal regularization parameter for ridge regression using cross-validation. The resulting algorithm is suited for large datasets and the computational cost does not depend on the size of the training set. We extend this algorithm to forward or backward feature selection in which the optimal regularization parameter is selected for each possible feature set. These feature selection algorithms yield solutions with a sparse weight matrix using a quadratic cost on the norm of the weights. A naive approach to optimizing the ridge regression parameter has a computational complexity of the order $O(R K N^{2} M)$ with $R$ the number of applied regularization parameters, $K$ the number of folds in the validation set, $N$ the number of input features and $M$ the number of data samples in the training set. Our implementation has a computational complexity of the order $O(KN^3)$ . This computational cost is smaller than that of regression without regularization $O(N^2M)$ for large datasets and is independent of the number of applied regularization parameters and the size of the training set. Combined with a feature selection algorithm the algorithm is of complexity $O(RKNN_s^3)$ and $O(RKN^3N_r)$ for forward and backward feature selection respectively, with $N_s$ the number of selected features and $N_r$ the number of removed features. This is an order $M$ faster than $O(RKNN_s^3M)$ and $O(RKN^3N_rM)$ for the naive implementation, with $N \ll M$ for large datasets. To show the performance and reduction in computational cost, we apply this technique to train recurrent neural networks using the reservoir computing approach, windowed ridge regression, least-squares support vector machines (LS-SVMs) in primal space using the fixed-size LS-SVM approximation and extreme learning machines.     

The Local Discontinuous Galerkin Method for the Fourth-Order Euler–Bernoulli Partial Differential Equation in One Space Dimension. Part II: A Posteriori Error Estimation

In this paper new a posteriori error estimates for the local discontinuous Galerkin (LDG) method for one-dimensional fourth-order Euler–Bernoulli partial differential equation are presented and analyzed. These error estimates are computationally simple and are obtained by solving a local steady problem with no boundary condition on each element. We use the optimal error estimates and the superconvergence results proved in Part I to show that the significant parts of the discretization errors for the LDG solution and its spatial derivatives (up to third order) are proportional to \((k+1)\) -degree Radau polynomials, when polynomials of total degree not exceeding \(k\) are used. These results allow us to prove that the \(k\) -degree LDG solution and its derivatives are \(\mathcal O (h^{k+3/2})\) superconvergent at the roots of \((k+1)\) -degree Radau polynomials. We use these results to construct asymptotically exact a posteriori error estimates. We further apply the results proved in Part I to prove that, for smooth solutions, these a posteriori LDG error estimates for the solution and its spatial derivatives at a fixed time \(t\) converge to the true errors at \(\mathcal O (h^{k+5/4})\) rate. We also prove that the global effectivity indices, for the solution and its derivatives up to third order, in the \(L^2\) -norm converge to unity at \(\mathcal O (h^{1/2})\) rate. Our proofs are valid for arbitrary regular meshes and for \(P^k\) polynomials with \(k\ge 1\) , and for periodic and other classical mixed boundary conditions. Our computational results indicate that the observed numerical convergence rates are higher than the theoretical rates. Finally, we present a local adaptive procedure that makes use of our local a posteriori error estimate.     

Thoughtful brute-force attack of the RERS 2012 and 2013 Challenges

The Rigorous Examination of Reactive Systems’ (rers) Challenges provide a forum for experimental evaluation based on specifically synthesized benchmark suites. In this paper, we report on our ‘brute-force attack’ of the rers 2012 and 2013 Challenges. We connected the rers problems to two state-of-the-art explicit state model checkers: LTSmin and Spin. Apart from an effective compression of the state vector, we did not analyze the source code of the problems. Our brute-force approach was successful: it won both editions of the rers Challenge.     

A note on the factorization conjecture

We give partial results on the factorization conjecture on codes proposed by Schützenberger. We consider a family of finite maximal codes $C$ over the alphabet $A = \{a, b\}$ and we prove that the factorization conjecture holds for these codes. This family contains $(p,4)$ -codes, where a $(p,4)$ -code $C$ is a finite maximal code over $A$ such that each word in $C$ has at most four occurrences of $b$ and $a^p \in C$ , for a prime number $p$ . We also discuss the structure of these codes. The obtained results once again show relations between factorizations of finite maximal codes and factorizations of finite cyclic groups.     

Improved Approximation of Linear Threshold Functions

We prove two main results on how arbitrary linear threshold functions ${f(x) = {\rm sign}(w \cdot x - \theta)}$ over the n-dimensional Boolean hypercube can be approximated by simple threshold functions. Our first result shows that every n-variable threshold function f is ${\epsilon}$ -close to a threshold function depending only on ${{\rm Inf}(f)^2 \cdot {\rm poly}(1/\epsilon)}$ many variables, where ${{\rm Inf}(f)}$ denotes the total influence or average sensitivity of f. This is an exponential sharpening of Friedgut’s well-known theorem (Friedgut in Combinatorica 18(1):474–483, 1998), which states that every Boolean function f is ${\epsilon}$ -close to a function depending only on ${2^{O({\rm Inf}(f)/\epsilon)}}$ many variables, for the case of threshold functions. We complement this upper bound by showing that ${\Omega({\rm Inf}(f)^2 + 1/\epsilon^2)}$ many variables are required for ${\epsilon}$ -approximating threshold functions. Our second result is a proof that every n-variable threshold function is ${\epsilon}$ -close to a threshold function with integer weights at most ${{\rm poly}(n) \cdot 2^{\tilde{O}(1/\epsilon^{2/3})}.}$ This is an improvement, in the dependence on the error parameter ${\epsilon}$ , on an earlier result of Servedio (Comput Complex 16(2):180–209, 2007) which gave a ${{\rm poly}(n) \cdot 2^{\tilde{O}(1/\epsilon^{2})}}$ bound. Our improvement is obtained via a new proof technique that uses strong anti-concentration bounds from probability theory. The new technique also gives a simple and modular proof of the original result of Servedio (Comput Complex 16(2):180–209, 2007) and extends to give low-weight approximators for threshold functions under a range of probability distributions other than the uniform distribution.