Search

In this paper, we develop algorithms to overcome the curse of dimensionality in non-convex state-dependent Hamilton-Jacobi partial differential equations (HJ PDEs) arising from optimal control and differential game problems. The subproblems are independent and they can be implemented in an embarrassingly parallel fashion. This is ideal for perfect scaling in parallel computing. The algorithm is proposed to overcome the curse of dimensionality [1,2] when solving HJ PDE. The major contribution of the paper is to change either the solving of a PDE problem or an optimization problem over a space of curves to an optimization problem of a single vector, which goes beyond the work of [40]. We extend the method in [7,9,15] , and conjecture a (Lax-type) minimization principle to solve state-dependent HJ PDE when the Hamiltonian is convex, as well as a (Hopf-type) maximization principle to solve state-dependent HJ PDE when the Hamiltonian is non-convex , as a generalization of the well-known Hopf formula in [18,25,50]. We showed the validity of the formula under restricted assumption for the sake of completeness, and would like to bring our readers to [62] which validates our conjectures in a more general setting. We conjectured the weakest assumption of our formula to hold is a pseudoconvexity assumption similar to one stated in [50]. Our method is expected to have application in control theory, differential game problems and elsewhere. [ABSTRACT FROM AUTHOR]

Highlights • A cointegration method is proposed to deal with heteroscedastic time series in SHM. • The TBATS (T rigonometric, B ox-Cox A RMA T rend, S easonal model is used to decompose a time series corrupted with seasonal noise. • A full-scale foot bridge is presented as one of the case studies. Abstract Heteroscedasticity, or time-dependent variance, is often observed in long-term monitoring data in the context of SHM, where it is normally induced by the seasonal variations of the ambient environment. In the effort to project out the environmental and operational variations, cointegration, a method originating in econometrics, has been successfully employed in various SHM studies. This paper will explore a possible enhanced approach to cointegration, to make it applicable to heteroscedastic data. The fact that the variance of heteroscedastic data is constantly changing has a significant negative impact on conventional damage detection algorithms, making it difficult to calculate accurate confidence intervals. Thus, in the current paper, an exponential smoothing method is presented to explore and deal with the complex seasonal patterns observed in SHM time series. More specifically, in this framework, a seasonally-corrupted time series can be decomposed into three components, namely, level, seasonal and residual terms. Subsequently, the series purged of seasonality will be fed into a cointegration analysis, in order to produce a more stationary residual series (damage indicator series). Two case studies, including a synthetic case and a real world SHM dataset, are demonstrated with results and discussions. [ABSTRACT FROM AUTHOR]

Highlights • The R-D relationship of the screen content video is related to video contents. On the basis of this fact, CTUs in screen content videos are classified into three types: T-CTUs, SI-CTUs and NI-CTUs according to their pixel activity and DCT coefficient distribution. • Disparate CTUs present vastly different R-D relationships. For this reason, instead of the unitive parameter update method in the R- λ model, the parameters used to code specific kind of CTU are updated according to the information of the last same kind of coded CTU rather than the last CTU. • Before assigning bits to each CTU, the bits allocated to text region, screen image region and nature image region are determined. When a scene change occurs, the bit allocation method which relied on the distortion and CTU number changes into the one only related to the number of CTUs. Abstract The popularity of 3D screen content videos like 3D animations calls for better coding performance of screen content videos. The exiting R- λ rate control model is designed to enable the coding performance of conventional nature videos, which can not accurately describe the Rate-Distortion (R-D) relationships of the screen content videos, especially for videos containing limited colors and sharper edges. This paper proposes a new rate control (RC) scheme which takes the divergent characteristics of text contents, screen images and nature images in screen content videos into consideration. In particular, the content-based rate control algorithm is developed at Coding Tree Unit (CTU) level, where CTUs are divided into three categories including Text-CTUs (T-CTUs), Screen Image-CTUs (SI-CTUs) and Nature Image-CTUs (NI-CTUs). Three R- λ models reflecting different R-D relationships of different CTUs are established, and the model parameters are updated on the basis of their own models. Furthermore, in view of the fact that continuity and mutability simultaneously exist in screen content videos, two bit allocation schemes for regions containing only one content are determined in this paper. Experimental results show that the proposed RC scheme achieves 0.749 dB BDPSNR increase under the Low Delay configuration and 0.637 dB BDPSNR increase under the Random Access configuration on average, compared to the default R- λ model in HEVC Screen Content Coding extension (HEVC-SCC) reference software. [ABSTRACT FROM AUTHOR]

Highlights • This paper focuses on the implementation of motion control for active suspension systems using a novel scheme of model-free finite-time tracking control method. • The proposed strategy facilitates the realization since the system plant modeling is not needed. • Unlike the existing control methods, the proposed disturbance compensator is continuous and finite-time convergent, which shows a great potential in application to practical suspension systems. • The advantage of the presented control algorithm is verified via comparative investigation, especially the comparison of the existing extended state observer-based feedback control scheme. • Comparative experimental studies are presented to confirm the effectiveness and superiority of the proposed control strategy over the traditional methods. Abstract This paper focuses on the implementation of motion control for active suspension systems using a novel scheme of model-free finite-time tracking control method. The proposed strategy facilitates the realization since the system plant modeling is not needed. Correspondingly, the suspension vertical dynamics including external disturbances are estimated by the time-delay estimation, and its estimated error is compensated by the integral sliding mode control scheme. Theoretical analysis proves that the sliding mode and desired system dynamics can achieve a finite time convergence performance with continuous control law. In active suspension control, the continuous control law contributes to preventing the unexpected chattering in practical implementation. The advantage of the presented control algorithm is verified via comparative investigation, especially the comparison of the existing extended state observer-based feedback control scheme, which requires a high-gain observer to realize the desired dynamics. Comparative experimental studies are presented to confirm the effectiveness and superiority of the proposed control strategy over the traditional methods. [ABSTRACT FROM AUTHOR]

Abstract Data Assimilation (DA) is an uncertainty quantification technique used to incorporate observed data into a prediction model in order to improve numerical forecasted results. Variational DA (VarDA) is based on the minimisation of a function which estimates the discrepancy between numerical results and observations. Operational forecasting requires real-time data assimilation. This mandates the choice of opportune methods to improve the efficiency of VarDA codes without loosing accuracy. Due to the scale of the forecasting area and the number of state variables used to describe the physical model, DA is a big data problem. In this paper, the Truncated Singular Value Decomposition (TSVD) is used to reduce the space dimension, alleviate the computational cost and reduce the errors. Nevertheless, a consequence is that important information is lost if the truncation parameter is not properly chosen. We provide an algorithm to compute the optimal truncation parameter and we prove that the optimal estimation reduces the ill-conditioning and removes the statistically less significant modes which could add noise to the estimate obtained from DA. In this paper, numerical issues faced in developing VarDA algorithm include the ill-conditioning of the background covariance matrix, the choice of a preconditioning and the choice of the regularisation parameter. We also show how the choice of the regularisation parameter impacts on the efficiency of the VarDA minimisation computed by the L-BFGS (Limited – Broyden Fletcher Goldfarb Shanno). Experimental results are provided for pollutant dispersion within an urban environment. Highlights • A Variational DA model is introduced for air flows prediction and pollution transport. • The optimal truncation parameter minimises condition number and Preconditioning Error. • The TSVD truncation parameter is independent from the knowledge of an exact solution. • The optimal truncation parameter does not require the whole spectrum of the matrix. [ABSTRACT FROM AUTHOR]

Abstract This paper addresses one of the main challenges of the conservative level set method, namely the ill-conditioned behavior of the normal vector away from the interface. An alternative formulation for reconstruction of the interface is proposed. Unlike commonly used methods, which rely on a unit normal vector, the Stabilized Conservative Level Set (SCLS) makes use of a modified normal vector with diminishing magnitude away from the interface. With the new formulation, in the vicinity of the interface the reinitialization procedure utilizes compressive flux and diffusive terms only in normal direction with respect to the interface, thus, preserving the conservative level set properties, while away from the interface the directional diffusion mechanism automatically switches to homogeneous diffusion. The proposed formulation is robust and general. It is especially well suited for use with the adaptive mesh refinement (AMR) approaches, since for computational accuracy high resolution is only required in the vicinity of the interface, while away from the interface low resolution simulations might be sufficient. All of the results reported in this paper are obtained using the Adaptive Wavelet Collocation Method, a general arbitrary order AMR-type method, which utilizes wavelet decomposition to adapt on steep gradients in the solution while retaining a predetermined order of accuracy. Numerical solution for a number of benchmark problems has been carried out to demonstrate the performance of the SCLS method. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we present a scheme for solving two-dimensional miscible displacement problems using Eulerian–Lagrangian localized adjoint methods and mixed finite element methods. Since only the velocity and not the pressure appears explicitly in the concentration equation, an Eulerian–Lagrangian localized adjoint method is used to solve the concentration equation and a mixed finite element method is used for the pressure equation. To linearize and decouple the mixed-method equations, we use a two-grid algorithm based on the Newton iteration method for this fully discrete problems. First, we solve the original nonlinear equations on the coarse grid, then, we solve the linearized problem on the fine grid using Newton iteration once. It is shown that the coarse grid can be much coarser than the fine grid and achieve asymptotically optimal approximation as long as the mesh sizes satisfy H = O (h 1 / 2) in this paper. [ABSTRACT FROM AUTHOR]

In the companion paper (Adler et al., 2017), we presented a characterization of the linear rank-width of distance-hereditary graphs, from which we derived an algorithm to compute it in polynomial time. In this paper, we investigate structural properties of distance-hereditary graphs based on this characterization. First, we prove that for a fixed tree T , every distance-hereditary graph of sufficiently large linear rank-width contains a vertex-minor isomorphic to T . We extend this property to bigger graph classes, namely, classes of graphs whose prime induced subgraphs have bounded linear rank-width. Here, prime graphs are graphs containing no splits. We conjecture that for every tree T , every graph of sufficiently large linear rank-width contains a vertex-minor isomorphic to T . Our result implies that it is sufficient to prove this conjecture for prime graphs. For a class Φ of graphs closed under taking vertex-minors, a graph G is called a vertex-minor obstruction for Φ if G ∉ Φ but all of its proper vertex-minors are contained in Φ . Secondly, we provide, for each k ⩾ 2 , a set of distance-hereditary graphs that contains all distance-hereditary vertex-minor obstructions for graphs of linear rank-width at most k . Also, we give a simpler way to obtain the known vertex-minor obstructions for graphs of linear rank-width at most 1. [ABSTRACT FROM AUTHOR]

Abstract The combination of adaptive feedforward with adaptive feedback disturbance compensation has been suggested since a number of years as a potential solution for improving the performance of active vibration control systems. Unfortunately, as shown in the present paper there is a strong coupling between adaptive feedback and adaptive feedforward which may lead to instabilities and new algorithms which take into account this interaction are proposed in the paper. These algorithms take advantage of the Youla-Kučera parametrization of the feedback controller and feedforward compensator. First, the adaptive feedback algorithm is presented alone. Then, the adaptive feedforward algorithm is designed taking into account the feedback controller's presence in the loop. Stability of the complete scheme is obtained by appropriately filtering the regressor vectors in order to take into account a strictly positive real condition. Experimental results obtained on a relevant test-bench illustrate the performance of this approach to active vibration control. Comparison with adaptive feedback alone, with adaptive feedforward alone and adaptive feedforward + fixed feedback are provided. [ABSTRACT FROM AUTHOR]

This paper presents fundamental algorithms for the computational theory of quadratic forms over number fields. In the first part of the paper, we present algorithms for checking if a given non-degenerate quadratic form over a fixed number field is either isotropic (respectively locally isotropic) or hyperbolic (respectively locally hyperbolic). Next we give a method of computing the dimension of an anisotropic part of a quadratic form. The second part of the paper is devoted to algorithms computing two field invariants: the level and the Pythagoras number. Ultimately we present an algorithm verifying whether two number fields have isomorphic Witt rings (i.e. are Witt equivalent). [ABSTRACT FROM AUTHOR]

The virtualization of modern computer networks introduces interesting new opportunities for a more flexible placement of network functions and middleboxes (firewalls, proxies, traffic optimizers, virtual switches, etc.). This paper studies approximation algorithms for the incremental deployment of a minimum number of middleboxes, such that capacity constraints at the middleboxes and length constraints on the communication routes are respected. Based on a new, purely combinatorial and rigorous proof of submodularity, we obtain our main result: a deterministic greedy approximation algorithm which only employs augmenting paths to serve future communication pairs. Hence, our algorithm does not require any changes to the locations of existing middleboxes or the preemption of previously served communication pairs when additional middleboxes are deployed. It is hence particularly attractive for incremental deployments. We prove that the achieved polynomial-time approximation bound is optimal, unless P = NP holds. This paper also initiates the study of a weighted problem variant, in which entire groups of nodes need to communicate via a middlebox, possibly at different rates. We present an LP relaxation and randomized rounding algorithm for this problem, leveraging an interesting connection to scheduling. We complement our formal results with a simulation study of a large set of synthetically generated instances. Our results indicate that the presented algorithms yield near-optimal solutions in practice. [ABSTRACT FROM AUTHOR]

As a useful formalism tool, graph grammars provide a rigorous but intuitive way to specify visual languages. This paper, based on the existing Edge-based Graph Grammar (EGG), proposes a new context-sensitive graph grammar formalism called the Temporal Edge-based Graph Grammar, or TEGG. TEGG introduces some temporal mechanisms to grammatical specifications, productions, operations and so on in order to tackle time-related issues. In the paper, formal definitions of TEGG are provided first. Then, a new parsing algorithm with a decidability proof is proposed to check the correctness of a given graph's structure, to analyze operations’ timing when needed, and to make the computer simulation of the temporal sequence in the graph available. Next, the complexity of the parsing algorithm is analyzed. Finally, a case study on an application with temporal requirements is provided to show how the parsing algorithm of TEGG works. [ABSTRACT FROM AUTHOR]

This paper deals with the implementation of high order semi-Lagrangian particle methods to handle high dimensional Vlasov–Poisson systems. It is based on recent developments in the numerical analysis of particle methods and the paper focuses on specific algorithmic features to handle large dimensions. The methods are tested with uniform particle distributions in particular against a recent multi-resolution wavelet based method on a 4D plasma instability case and a 6D gravitational case. Conservation properties, accuracy and computational costs are monitored. The excellent accuracy/cost trade-off shown by the method opens new perspective for accurate simulations of high dimensional kinetic equations by particle methods. [ABSTRACT FROM AUTHOR]

In this paper, we study the notion of special ideals. We generalize the results on those as well as the algorithm obtained for finite dimensional power series rings by Mordechai Katzman and Wenliang Zhang to finite dimensional polynomial rings. [ABSTRACT FROM AUTHOR]

In this paper we describe the method which we applied to successfully compute the primary decomposition of a certain ideal coming from applications in combinatorial algebra and algebraic statistics regarding conditional independence statements with hidden variables. While our method is based on the algorithm for primary decomposition by Gianni, Trager and Zacharias, we were not able to decompose the ideal using the standard form of that algorithm, nor by any other method known to us. [ABSTRACT FROM AUTHOR]

In this paper we present new techniques for improving the computation of strong Gröbner bases over a principal ideal ring R. More precisely, we describe how to lift a strong Gröbner basis along a canonical projection R → R / n , n ≠ 0 , and along a ring isomorphism R → R 1 × R 2. We then apply this to the computation of strong Gröbner bases over a non-trivial quotient of a principal ideal domain R / n R. The idea is to run a standard Gröbner basis algorithm pretending R / n R to be field. If we discover a non-invertible leading coefficient c , we use this information to try to split n = a b with coprime a , b. If this is possible, we recursively reduce the original computation to two strong Gröbner bases computations over R / a R and R / b R respectively. If no such c is discovered, the returned Gröbner basis is already a strong Gröbner basis for the input ideal over R / n R. [ABSTRACT FROM AUTHOR]

The ring of covariants of binary form is isomorphic to the ring of regular symmetric bracket polynomials in homogenized roots, which are obtained by symmetrization of regular bracket polynomials. In this paper, we give an algorithm for computing all cyclically standard bracket monomials of arbitrary degree. These monomials form a basis of the vector space of the regular bracket polynomials of a given degree. We also characterize the elemental bracket monomial of degree 2 in terms of graph theory. [ABSTRACT FROM AUTHOR]

It is known [6,14,19] that if Ω ⊂ R d belongs to a class of k -tiling domains when translated by a lattice Λ, there exists a Riesz basis of exponentials for L 2 (Ω) constructed using k translates of the dual lattice Λ ⁎. In this paper, we give an explicit construction of the corresponding biorthogonal dual Riesz basis. We also extend the iterative reconstruction algorithm introduced in [11] to this setting. [ABSTRACT FROM AUTHOR]

Quality of service (QoS) provision has become an important aspect of high-performance computing interconnection networks. Proof of that is the inclusion of mechanisms targeted to the provision of QoS by the main interconnection technologies such as Gigabit Ethernet, Infiniband (IB) and Omni-Path (OPA). A key component of QoS provision is the output scheduling algorithm, which determines when a packet should be transmitted. An ideal scheduling algorithm should satisfy two main properties: good end-to-end latency and implementation simplicity. Table-based schedulers are able to provide these two properties, and because of this, IB and OPA have implemented this approach. In this paper, we present a comparative study in terms of QoS provision between these two dominating interconnection technologies. Those interconnection technologies are also two examples of non-hierarchical and hierarchical switch architectures, respectively, which gives the results of this study greater significance. In order to carry out the study, the Deficit Table scheduler (DTable) has been used. DTable is a table-based scheduling algorithm which offers a good balance between end-to-end latency and implementation cost. • Implementation and modeling a non-hierarchical and a hierarchical switch. • Description and implementation of QoS Omni-Path and InfiniBand mechanisms. • Adaptation of the Deficit Table Output Scheduler for both architectures. • Comparison of both switch architectures in terms of QoS provision. • Hierarchical architectures have better latency results than non-hierarchical ones. [ABSTRACT FROM AUTHOR]

A watermark hidden in an image is retrieved differently from the original watermark due to the frequently used rounding approach. The simple rounding will cause numerous errors in the embedded watermark especially when it is large. A novel technique based on genetic algorithms (GAs) is presented in this paper to correct the rounding errors. The fundamental is to adopt a fitness function for choosing the best chromosome which determines the conversion rule of real numbers into integers during the cosine transformation. Experimental results show that the dramatic improvement in reducing the errors is successful when GAs are used in decision making. Furthermore, we develop an initial chromosome by comparing the difference between the original image and the rounded watermarked image to speed up the process. In additional to correct fragile-watermarking rounding errors, our algorithm can also be applied in robust watermarking to achieve higher watermarked image quality. [ABSTRACT FROM AUTHOR]

We describe an algorithm for classifying the closed subsets of a root system, up to conjugation by the associated Weyl group. Our algorithm is implemented in the language of the computer algebra system GAP 4. We discuss the implementation and give runtimes on some sample inputs. The classification of the closed subsets of an irreducible root system is closely related to the classification of the regular subalgebras, up to inner automorphism, of the corresponding simple Lie algebra. We show how to obtain the regular subalgebras corresponding to a given closed set for the root systems of rank 3. The version of this paper on the arxiv has tables describing the subalgebras that were obtained. [ABSTRACT FROM AUTHOR]

This paper provides a new algorithm for the formal reduction of linear differential systems with Laurent series coefficients. We show how to obtain a decomposition of Balser, Jurkat and Lutz using eigenring techniques. This allows us to establish structural information on the obtained indecomposable subsystems and retrieve information on their invariants such as ramification. We show why classical algorithms then perform well on these subsystems. We also give precise estimates of the precision on the power series which is required in each step of our algorithm. The algorithm is implemented in Maple and examples are given in Saade (2018). [ABSTRACT FROM AUTHOR]

In this paper, we first prove that when the associated graph of a polynomial set is chordal, a particular triangular set computed by a general algorithm in top-down style for computing the triangular decomposition of this polynomial set has an associated graph as a subgraph of this chordal graph. Then for Wang's method and a subresultant-based algorithm for triangular decomposition in top-down style and for a subresultant-based algorithm for regular decomposition in top-down style, we prove that all the polynomial sets appearing in the process of triangular decomposition with any of these algorithms have associated graphs as subgraphs of this chordal graph. These theoretical results can be viewed as non-trivial polynomial generalization of existing ones for sparse Gaussian elimination, inspired by which we further propose an algorithm for sparse triangular decomposition in top-down style by making use of the chordal structure of the polynomial set. The effectiveness of the proposed algorithm for triangular decomposition, when the polynomial set is chordal and sparse with respect to the variables, is demonstrated by preliminary experimental results. [ABSTRACT FROM AUTHOR]

We consider the problem of finding the isolated common roots of a set of polynomial functions defining a zero-dimensional ideal I in a ring R of polynomials over C. Normal form algorithms provide an algebraic approach to solve this problem. The framework presented in Telen et al. (2018) uses truncated normal forms (TNFs) to compute the algebra structure of R / I and the solutions of I. This framework allows for the use of much more general bases than the standard monomials for R / I. This is exploited in this paper to introduce the use of two special (non-monomial) types of basis functions with nice properties. This allows us, for instance, to adapt the basis functions to the expected location of the roots of I. We also propose algorithms for efficient computation of TNFs and a generalization of the construction of TNFs in the case of non-generic zero-dimensional systems. The potential of the TNF method and usefulness of the new results are exposed by many experiments. [ABSTRACT FROM AUTHOR]

In this paper we state and explain techniques useful for the computation of strong Gröbner and standard bases over Euclidean domains: First we investigate several strategies for creating the pair set using an idea by Lichtblau. Then we explain methods for avoiding coefficient growth using syzygies. We give an in-depth discussion on normal form computation resp. a generalized reduction process with many optimizations to further avoid large coefficients. These are combined with methods to reach GCD-polynomials at an earlier stage of the computation. Based on various examples we show that our new implementation in the computer algebra system Singular is, in general, more efficient than other known implementations. [ABSTRACT FROM AUTHOR]

Two new efficient algorithms for computing greatest common divisors (gcds) of parametric multivariate polynomials over k [ U ] [ X ] are presented. The key idea of the first algorithm is that the gcd of two non-parametric multivariate polynomials can be obtained by dividing their product by the generator of the intersection of two principal ideals generated by the polynomials. The second algorithm is based on another simple insight that the gcd can be extracted using the generator of the ideal quotient of a polynomial with respect to the second polynomial. Since the ideal intersection and ideal quotient in these cases are also principal ideals, their generators can be obtained by computing minimal Gröbner bases of the ideal intersection and ideal quotient, respectively. To avoid introducing new variables which can adversely affect the efficiency, minimal Gröbner bases computations are performed on modules. Both of these constructions generalize to the parametric case as shown in the paper. Comprehensive Gröbner system constructions are used for the parametric ideal intersection and ideal quotient using the Kapur-Sun-Wang's algorithm. It is proved that whether in a minimal comprehensive Gröbner system of a parametric ideal intersection or in that of a parametric ideal quotient, each branch of the specializations corresponds to a principal parametric ideal with a single generator. Using this generator, the parametric gcd of that branch is obtained by division. For the case of more than two parametric polynomials, we can use the above two algorithms to compute gcds recursively, and get an extended algorithm by generalizing the idea of the second algorithm. Algorithms do not suffer from having to apply expensive steps such as ensuring whether parametric polynomials are primitive w.r.t. the main variable as used in both the algorithms proposed by Nagasaka (ISSAC, 2017). The resulting algorithms are not only conceptually simple to understand but are more efficient in practice. The proposed algorithms and both of Nagasaka's algorithms have been implemented in Singular, and their performance is compared on a number of examples. [ABSTRACT FROM AUTHOR]

Graphics Processing Units technology (GPU) and CUDA architecture are one of the most used options to adapt machine learning techniques to the huge amounts of complex data that are currently generated. Biclustering techniques are useful for discovering local patterns in datasets. Those of them that have been implemented to use GPU resources in parallel have improved their computational performance. However, this fact does not guarantee that they can successfully process large datasets. There are some important issues that must be taken into account, like the data transfers between CPU and GPU memory or the balanced distribution of workload between the GPU resources. In this paper, a GPU version of one of the fastest biclustering solutions, BiBit, is presented. This implementation, named gBiBit, has been designed to take full advantage of the computational resources offered by GPU devices. Either using a single GPU device or in its multi-GPU mode, gBiBit is able to process large binary datasets. The experimental results have shown that gBiBit improves the computational performance of BiBit, a CPU parallel version and an early GPU version, called ParBiBit and CUBiBit, respectively. gBiBit source code is available at https://github.com/aureliolfdez/gbibit. • gBiBit is the first binary biclustering method that can process large datasets. • gBiBit development includes a novel methodology to take full advantage of the GPU device resources. • gBiBit solves the memory issues in GPU technology when large datasets must be processed. • gBiBit also has a multi-GPU version that allow to use multiple GPU devices in a balanced way. • gBiBit source code is available at https://github.com/aureliolfdez/gbibit. [ABSTRACT FROM AUTHOR]

Cloud computing provides scalable network services and makes network management more flexible by combining Software-Defined Networking (SDN). Through the northbound interface (e.g., REST API) offered by the SDN controller, users can easily deploy diversified applications to access the network resources. However, exploiting the openness of the northbound interface, malicious applications abuse APIs to launch hostile attacks, which poses serious threats to the network. In this paper, we propose SEAPP, a secure application management framework based on REST API access control. Our main idea is to granularly manage application permissions and encrypt REST API calls to defend against malicious attacks. SEAPP includes two components: 1) permissions detection engine identifies the facticity of application permissions by analyzing permission manifests and byte codes and further identifies the legality of permissions with constructed sensitive API list; 2) registration authorization engine executes encrypted registration between applications and controller by virtue of NTRU algorithm and authorizes applications to call the requested REST APIs based on their risk levels after securely authenticating them. Besides, SEAPP is a lightweight logic architecture between application plane and control plane and supports quick deployment and reconfiguration in runtime. Both theoretical analysis and evaluation results show the security and effectiveness of SEAPP. Besides, SEAPP introduces negligible CPU and memory overheads. • The fidelity and legality of application permissions are identified. • Application registration information is encrypted by NTRU. • A dynamic REST APIs authorization is developed. [ABSTRACT FROM AUTHOR]

Interactive consistency is the problem in which n distinct nodes, each having its own private value, where up to t may be Byzantine, run an algorithm that allows all non-faulty nodes to infer the values of each other node. This problem is relevant to critical applications that rely on the combination of the opinions of multiple peers to provide a service. Examples include monitoring a content source to prevent equivocation or to track variability in the content provided, and resolving divergent state amongst the nodes of a distributed system. Previous works assume a fully synchronous system, where one can make strong assumptions such as negligible message delivery delays and/or detection of absent messages. However, practical, real-world systems are mostly asynchronous, i.e., they exhibit only some periods of synchrony during which message delivery is timely, thus requiring a different approach. In this paper, we present a thorough study of practical interactive consistency. We leverage the vast prior work on broadcast and Byzantine consensus algorithms to design, implement and evaluate a set of randomized algorithms, with only a single synchronization barrier and varying message complexities, that can be used to achieve interactive consistency in real-world distributed systems. We present formal proofs of correctness and message complexity of our proposed algorithms. We provide a complete, open-source implementation of each proposed interactive consistency algorithm by building a multi-layered software stack of algorithms that includes several broadcast algorithms, as well as a binary and a multi-valued consensus algorithm. Most of these algorithms have never been implemented and evaluated in a real system before. Finally, we analyze the performance of our suite of algorithms experimentally by testing both single instance and multiple parallel instances of each alternative and present a case study of achieving interactive consistency in a real-world distributed e-voting system. • Algorithms for interactive consistency in practical, real-world systems. • Formal proofs of correctness for the proposed algorithms. • Open-source implementation of the proposed algorithms. • Empirical evaluation of open-source prototype and e-voting case study. [ABSTRACT FROM AUTHOR]

Rendezvous algorithms encode a communication pattern that is useful when processors sending data do not know who the receiving processors should be, or vice versa. The idea is to define an intermediate decomposition where datums from different sending processors can "rendezvous" to perform a computation, in a manner that both the senders and eventual receivers of the results can identify the appropriate rendezvous processor. Originally designed for interpolating between overlaid grids with independent parallel decompositions (Plimpton et al., 2004), we have recently found rendezvous algorithms useful for a variety of operations in particle- or grid-based simulation codes when running large problems on large numbers of processors. In particular, we show they can perform well when a load-balanced intermediate decomposition is randomized and not spatial, requiring all-to-all communication to move data between processors. In this case rendezvous algorithms leverage the large bisection communication bandwidths which parallel machines provide. We describe how rendezvous algorithms work in a scientific computing context and give specific examples for molecular dynamics and Direct Simulation Monte Carlo codes which result in dramatic performance improvements versus simpler algorithms which do not scale as well. We explain how a generic rendezvous algorithm can be implemented, and also point out similarities with the MapReduce paradigm popularized by Google and Hadoop. • This paper explains how parallel rendezvous algorithms work in the context of large-scale scientific modeling and simulation codes. • It gives several examples of such algorithms. • It presents performance gains of the new algorithms relative to previously used simpler algorithms which were less scalable. [ABSTRACT FROM AUTHOR]

With the advent of the Industry 4.0 era, the development of smart cities based on the Internet of Things (IoT) has reached a new level. As a key component of the Internet of Things (IoT), the security of wireless sensor networks (WSN) has received widespread attention. Among them, Energy Internet, as an important part to support the construction of smart cities, its security and reliability research is becoming more and more important. In the Energy Internet, distributed energy transaction model is a promising approach to replace the traditional centralized transaction model and has become the leading direction of development in energy trading. As the underlying support, blockchain technology is attracting more and more attention due to its advantages, i.e., integrity and non-repudiation. However, most blockchain-based trading models face the problem of privacy disclosure. In this paper, to solve this problem, Ciphertext-Policy Attribute-Based Encryption (CP-ABE) is introduced as the core algorithm to reconstruct the transaction model. Specifically, we build a general model for distributed transactions called PP-BCETS (Privacy-preserving Blockchain Energy Trading Scheme). It can achieve fine-grained access control through transaction arbitration in the ciphertext form. This design can maximize the protection of privacy information, and considerably improve the security and reliability of the transaction model. Additionally, a credibility-based equity proof consensus mechanism is proposed in PP-BCETS, which can greatly increase the operation efficiency. The security analysis and experimental evaluations are conducted to prove the validity and practicability of our proposed scheme. • Secure and privacy-preserving energy trading scheme is proposed. • ABE- and blockchain-based energy trading. • credibility-based equity proof consensus mechanism. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents a detailed description of a real-time correlation-based stereo algorithm running completely on the graphics processing unit (GPU). This is important since it allows to free up the main processor for other tasks including high-level interpretation of the stereo results. We first introduce a two-view stereo algorithm that includes some advanced features such as adaptive windows and cross-checking. Then we extend it using a plane-sweep approach to allow multiple frames without rectification. By taking advantage of advanced features of recent GPUs the proposed algorithm runs in real-time. Our implementation running on an ATI Radeon 9800 graphics card achieves up to 289 million disparity evaluations per second including all the overhead to download images and read-back the disparity map, which is several times faster than commercially available CPU-based implementations. [Copyright &y& Elsevier]

• A new compounding imaging algorithm integrating amplitude and phase information of signal based on Lamb wave phased array is proposed. • Sigmoid function with variable gradient is used for establishing the nonlinear mapping between imaging index and phase difference. • The proposed imaging algorithm is validated on plates of different materials and dimensions with multiple types of defects. • The proposed imaging algorithm can effectively improve the signal-to-noise ratio of the images and suppress artifacts, implementing imaging without threshold. Aimed at improving the imaging performance of Lamb wave phased array based on Delay-and-Sum (DAS) of signal amplitude, a compounding imaging algorithm integrating amplitude and phase information of signal is proposed in this paper. By applying back propagation dispersion compensation, the pulse echoes caused by defects will be in-phase with the excitation signal, implementing signal focusing. In the proposed imaging algorithm, the amplitude imaging index is calculated by classical total focusing method (TFM) and the phase imaging index is calculated by phase coherence factor (PCF), which establishes the nonlinear mapping between imaging index and phase difference by sigmoid function with variable gradient. The final imaging results are the compound of two imaging indexes. The experimental validation is carried out on plates of different materials and dimensions with multiple types of defects based on uniform linear array. Compared with the imaging results of conventional TFM, the proposed imaging algorithm can effectively improve the signal-to-noise ratio (SNR) of the images and suppress artifacts, implementing threshold-free imaging. [ABSTRACT FROM AUTHOR]

[Display omitted] The unstable statuses in machining, such as chatter and severe forced vibration, limit manufacturing productivity and quality. Although there have been plentiful studies on the on-line sensing signals and off-line surface images to identify these statuses qualitatively, the quantification of chatter severity, which is of great significance on machining stability, has been rarely reported. Workpiece surface morphology is the direct result and thus the objective criteria of unstable machining. This paper proposes a new algorithm to quantify the chatter status based on the milled surface image analysis of end-milling. Besides, the proposed method can also identify the stable, forced vibration, and chatter statuses. Specifically, this proposed algorithm extracts two indexes, called Index_Dmean and Index_Emean , via processing the milled surface image. The definitions and calculations of these two indexes are given in Section 2. Index_Dmean is used to differentiate stable and unstable surfaces and quantify the severity of chatter status, and Index_Emean can distinguish between forced vibration and chatter surfaces. Experimental results demonstrate the availability of the proposed algorithm on the chatter quantification and milling instability classification performance. In addition, an applicable on-line vision system with satisfying performance based on the algorithm is developed. [ABSTRACT FROM AUTHOR]

With the development of artificial intelligence, deep reinforcement learning (DRL) has been applied for fiber laser. In this paper, the intelligent passively mode-locked fiber laser (PMLFL) with the Soft Actor–Critic (SAC) algorithm is reported. The SAC algorithm is a DRL algorithm with random policy, which combines the Actor–Critic framework and the maximum entropy. The agent learns the logic of mode-locking by outputting actions and inputting states of the laser. Due to the maximum entropy model, more exploration is encouraged, which means that multiple policies can be learned to maximize the reward, and the robustness is enhanced accordingly. The results show that the logic learned by the agent is similar to that of human. In 80 random initial state of polarization mode-locked tests, 37 explorations are needed on average, and the frequency of achieving mode-locked state exceeds 0.8 within 60 explorations. Further, the laser system can be monitored or controlled remotely, which expands the application scenarios. • Passively mode-locked fiber laser based on the Soft Actor–Critic (SAC) algorithm is proposed. • SAC algorithm is more exploratory and thus more robust. • The laser system based on SAC algorithm can resist the change of environment and realize mode-locking. • The experimental results prove the high stability of SAC algorithm. [ABSTRACT FROM AUTHOR]

Object drift determination is a crucial issue in long-term tracking. Most existing object drift determination criteria require manually selecting different thresholds on different datasets to determine whether the object is lost. In this case, choosing the appropriate threshold is a complex problem. An object drift determination network based on dual-template joint decision-making is proposed to address this issue. The proposed object drift determination network not only does not require selection of thresholds on different datasets, and can be used as a plug-and-play module of short-term visual tracking algorithm to achieve long-term visual tracking tasks with good generalization ability. The proposed object drift determination network is applied to four short-term baseline trackers and constructs four long-term visual tracking algorithms. Experimental results verify that all four improved algorithms significantly improve long-term visual tracking performance compared to the original algorithms. In addition, the determined speed of the object drift determination network proposed in this paper reaches 111 FPS, which has little effect on the long-term visual tracking speed. • New drift determination network without threshold selection is proposed. • New template update criterion is proposed to ensure the quality of templates. • Capable of acting as a plug-and-play module for most basic trackers. • The effectiveness of the proposed method is verified on five public datasets. [ABSTRACT FROM AUTHOR]

• A layout plane is a closed loop surrounded by layout keypoints. • The wall structure can be parametrization as an undirected graph. • Layout keypoint prediction is relative to human pose estimation. • Cuboid room assumption is limited in real life. Room layout estimation aims to predict the spatial structure of a room from a single image. Most existing methods relying on 2D cues are suitable for cuboid rooms, but non-cuboid rooms. 3D layout estimation methods can reconstruct 3D models of general rooms, but they are trained with depth information on high collection costs, consume large computation resources, and run slowly. This paper considers an undirected graph representation method of the general room layouts, which includes cuboid and non-cuboid rooms consisting of a single ceiling, a single floor, and multiple walls. To this end, we first predict the positions of the layout vertices and then use the network automatically learn the connection relationship between the vertices. The final layout is obtained through a simple layout inference post-processing algorithm. The experimental results both on cuboid and non-cuboid datasets validate the effectiveness and efficiency of our method. The code is available at https://github.com/Hui-Yao/2D-graph-layout-estimation. [ABSTRACT FROM AUTHOR]

In this paper, we prove that the general CNF satisfiability problem can be solved in O ⁎ (1.0638 L) time, where L is the length of the input CNF-formula (i.e., the total number of literals in the formula), which improves the previous result of O ⁎ (1.0652 L) obtained in 2009. Our algorithm was analyzed by using the measure-and-conquer method. Our improvements are mainly attributed to the following two points: we carefully design branching rules to deal with degree-5 and degree-4 variables to avoid previous bottlenecks; we show that some worst cases will not always happen, and then we can use an amortized technique to get further improvements. In our analyses, we provide some general frameworks for analysis and several lower bounds on the decreasing of the measure to simplify the arguments. These techniques may be used to analyze more algorithms based on the measure-and-conquer method. [ABSTRACT FROM AUTHOR]

Pairing-friendly curves with the lack of twists, such as BW13-P310 and BW19-P286 , have been receiving attention in pairing-based cryptographic protocols as they provide fast operation in the first pairing subgroup G 1 at the 128-bit security level. However, they also incur a performance penalty for hashing to G 2 simultaneously since G 2 is totally defined over a full extension field. Furthermore, the previous methods for hashing to G 2 focus on pairing-friendly curves admitting a twist, which can not be employed for our selected curves. In this paper, we propose a general method for hashing to G 2 on curves with the lack of twists. More importantly, we further optimize the general algorithm on curves with non-trivial automorphisms, which is certainly suitable for BW13-P310 and BW19-P286. Theoretical estimations show that the latter would be more efficient than the former. For comparing the performance of the two proposed algorithms in detail, high speed software implementation over BW13-P310 is also provided on a 64-bit processor. Experimental results show that the general algorithm can be sped up by up to 88% if the computational cost of cofactor multiplication for G 2 is only considered, while the improved method is up to 71% faster than the general one for the whole process. [ABSTRACT FROM AUTHOR]

Filterless optical networks (FON) are attracting attention because of their low-cost characteristics. However, removing active devices forces the signal to be broadcast on all output ports, wasting a significant amount of spectrum resources. In order to maintain the low-cost advantage and save more spectrum resources, this paper studies the routing, modulation, and spectrum assignment (RMSA) problem in semi-filterless optical networks. For this problem, we propose a spectrum assignment algorithm based on adaptive modulation scheme with minimum link and boundary distance (ML-M-MTBD). The algorithm selects the path that occupies the minimal number of links (ML) for spectrum assignment during the routing process and combines it with a variable adaptive modulation scheme (VAMS) between fiber trees. During the spectrum assignment process, the algorithm divides the frequency spectrum resources into two regions, calculates the distance from the frequency spectrum block to the two boundaries of the spectrum resources to be assigned, and selects the position corresponding to the shorter distance to the boundary for spectrum assignment. We conducted simulations on German-Net and Henan-Net, and compared our algorithm with two existing algorithms, the first-fit algorithm and the best-fit algorithm. The simulation results show that the proposed algorithm has a lower blocking probability. • Combining two optimization metrics of routing and spectrum assignment: (1) L: Link occupancy; (2) BD: Boundary distance of the spectrum block, we propose an algorithm for minimum link and boundary distance spectrum assignment. • Reduced the request blocking probability in the semi-filterless network. [ABSTRACT FROM AUTHOR]

Young tableaux carry an associative product, described by the Schensted algorithm. They thus form a monoid Pl , called plactic. It is central in numerous combinatorial and algebraic applications. In this paper, the tableaux product is shown to be completely determined by an idempotent braiding σ on the (much simpler!) set of columns Col. Here a braiding is a set-theoretic solution to the Yang–Baxter equation. As an application, we identify the Hochschild cohomology of Pl , which resists classical approaches, with the more accessible braided cohomology of (Col , σ). The cohomological dimension of Pl is obtained as a corollary. Also, the braiding σ is proved to commute with the classical crystal reflection operators s i. [ABSTRACT FROM AUTHOR]

In this paper we propose a primal-dual dynamical approach to the minimization of a structured convex function consisting of a smooth term, a nonsmooth term, and the composition of another nonsmooth term with a linear continuous operator. In this scope we introduce a dynamical system for which we prove that its trajectories asymptotically converge to a saddle point of the Lagrangian of the underlying convex minimization problem as time tends to infinity. In addition, we provide rates for both the violation of the feasibility condition by the ergodic trajectories and the convergence of the objective function along these ergodic trajectories to its minimal value. Explicit time discretization of the dynamical system results in a numerical algorithm which is a combination of the linearized proximal method of multipliers and the proximal ADMM algorithm. [ABSTRACT FROM AUTHOR]

In this paper we present a matricial result that generalizes Hironaka's game and Perron transforms simultaneously. We also show how one can deduce the various forms in which the algorithm of Perron appears in proofs of local uniformization from our main result. [ABSTRACT FROM AUTHOR]

This paper studies the problem of finding a path center on a tree in which vertex weights are uncertain and the uncertainty is described by given intervals. It is required to find a minmax regret solution, which minimizes the worst-case loss in the objective function. An O (n log n)-time algorithm is presented, improving the previous upper bound of O (n 2). [ABSTRACT FROM AUTHOR]

In public key encryption with keyword search (PEKS), a secure channel is required in order to send trapdoors to the server, whereas in secure-channel free PEKS (SCF-PEKS), no such secure channel is required. In this paper, we propose a generic construction of SCF-PEKS with multiple keywords (SCF-MPEKS) from hidden vector encryption, tag-based encryption, and a one-time signature. Our generic construction provides adaptive security, where the test queries are allowed in the security model, and does not require random oracles. In addition to providing an instantiation of our generic construction, which is the first adaptive secure SCF-MPEKS scheme in the standard model, we implement the SCF-MPEKS scheme by using the PBC library. Moreover, we extend the Boneh-Waters range search technique, and show that the running time of our encryption algorithm is approximately twice as fast as that of the Boneh-Waters encryption algorithm. [ABSTRACT FROM AUTHOR]

Fog computing is an emerging paradigm that brings computing capabilities closer to distributed IoT devices, which provides networking services between end devices and traditional cloud data centers. One important mission is to further reduce the monetary cost of fog resources while meeting the ever-growing demands of multiple users. In this paper, we focus on minimizing the total cost for multiple mobile users to provide an efficient resource provisioning scheme in fog computing. The total cost includes two aspects: the replication cost and the transmission cost. We consider three cases for the resource provision problem by focusing on different cost models. First, one simple case where users can only upload one replication is discussed, and an optimal solution is proposed by converting the original problem into a bipartite graph matching. Then we consider a more complicated case in which each user can upload multiple replications on fog nodes in the resource provisioning. Specifically, two models are discussed: the 0–1 transmission cost model and the different transmission cost model. For the 0–1 transmission cost model, each user can upload multiple replications with a constant transmission cost, and one optimal greedy solution is proposed. For the different transmission cost model, the transmission cost is related to the distance of each pair of fog nodes. This problem is proven to be NP-hard. We first propose a non-adaptive algorithm which is proved to be bounded by 2 3 W + 1 3 O P T. Another 3 + ϵ -approximation algorithm is proposed based on local search, which has better performance with higher complexity. Extensive simulations also prove the efficiency of our schemes. • We consider the resource provision problem for users with cost minimization and model the identified problem by considering two types of cost: replication cost and transmission cost. We first discuss a simple case, and one optimal solution is proposed. We then consider a more complicated case in which each user can upload multiple replications on fog nodes in the provisioning process. Two models are discussed: the 0–1 transmission cost model and the different transmission cost model. • We propose an optimal solution for the 0–1 transmission cost model. Then we prove that the problem under the different transmission cost model is NP-hard. We first propose a non-adaptive algorithm which is proved to be bounded by 2 3 W + 1 3 O P T. Another 3 + ϵ -approximation algorithm is proposed based on local search, which has better performance with higher complexity. • Various simulations were conducted to compare our joint optimization methods with several state-of-the-art ones based on two real datasets: the Mobike dataset and the Microsoft GPS trajectory dataset. The results are shown from different perspectives to provide conclusions. [ABSTRACT FROM AUTHOR]

Large-scale data-intensive applications provide services to users by routing service requests to geographically distributed data centers interconnected by Internet links. In order to achieve good reliability and data access latency performance, cloud service providers often simultaneously place multiple copies of the data in different data centers. The network communication required for updating the multiple data copies incurs an operational cost. At the same time, the penalty incurred by the Service Level Agreement (SLA) violation for data access from the data centers also imposes an operational cost on the service providers. In this paper, we tackle the problem of data placement in distributed data centers with the aim to minimize the operational cost incurred by delay SLA violation penalty and inter-data center network communication, assuming each data has K data replicas. We propose a K-level Cluster-based Data Placement algorithm (K-CDP) for the problem. The algorithm solves the linear programming relaxation and dual programming problems corresponding to the problem of minimizing SLA violation penalty cost caused by placing a replica of each data in a data center. Based on the obtained solutions, the algorithm clusters the data so that the data with similar placeable data centers form a data cluster. For the data in each cluster, the algorithm selects K data centers to minimize the operational cost. We prove that algorithm K-CDP is 2-approximation to the data placement problem. Our simulation results demonstrate that the proposed algorithm can effectively reduce the penalty cost incurred by delay SLA violation, the network communication cost, and the operational cost of data centers. • We tackle the data placement problem to minimize SLA violation and network communication cost. • We propose an algorithm which is proved to be 2-approximation to the data placement problem. • The simulation results show the proposed algorithm is effective and promising. [ABSTRACT FROM AUTHOR]

For a finite group G , the Hurwitz space H r , g i n (G) is the space of genus g covers of the Riemann sphere with r branch points and the monodromy group G. In this paper, we give a complete list of primitive genus one systems of affine type. That is, we assume that G is a primitive group of affine type. Under this assumption we determine the braid orbits on the suitable Nielsen classes, which is equivalent to finding connected components in H r , 1 i n (G). Furthermore, we give a new algorithm for computing large braid orbits on Nielsen classes. This algorithm utilizes a correspondence between the components of H r , 1 i n (G) and H r , 1 i n (M) , where M is the point stabilizer in G. [ABSTRACT FROM AUTHOR]

In an earlier article (Bostan et al., 2017), with Carlos D'Andrea, we described explicit expressions for the coefficients of the order- d polynomial subresultant of (x − α) m and (x − β) n with respect to Bernstein's set of polynomials { (x − α) j (x − β) d − j , 0 ≤ j ≤ d } , for 0 ≤ d < min ⁡ { m , n }. The current paper further develops the study of these structured polynomials and shows that the coefficients of the subresultants of (x − α) m and (x − β) n with respect to the monomial basis can be computed in linear arithmetic complexity, which is faster than for arbitrary polynomials. The result is obtained as a consequence of the amazing though seemingly unnoticed fact that these subresultants are scalar multiples of Jacobi polynomials up to an affine change of variables. [ABSTRACT FROM AUTHOR]

The Berlekamp–Massey–Sakata algorithm and the Scalar-FGLM algorithm both compute the ideal of relations of a multidimensional linear recurrent sequence. Whenever quering a single sequence element is prohibitive, the bottleneck of these algorithms becomes the computation of all the needed sequence terms. As such, having adaptive variants of these algorithms, reducing the number of sequence queries, becomes mandatory. A native adaptive variant of the Scalar-FGLM algorithm was presented by its authors, the so-called Adaptive Scalar-FGLM algorithm. In this paper, our first contribution is to make the Berlekamp–Massey–Sakata algorithm more efficient by making it adaptive to avoid some useless relation testings. This variant allows us to divide by four in dimension 2 and by seven in dimension 3 the number of basic operations performed on some sequence family. Then, we compare the two adaptive algorithms. We show that their behaviors differ in a way that it is not possible to tweak one of the algorithms in order to mimic exactly the behavior of the other. We detail precisely the differences and the similarities of both algorithms and conclude that in general the Adaptive Scalar-FGLM algorithm needs fewer queries and performs fewer basic operations than the Adaptive Berlekamp–Massey–Sakata algorithm. We also show that these variants are always more efficient than the original algorithms. [ABSTRACT FROM AUTHOR]