Search

The aim of this paper is to present an explicit reduction algorithm for Hilbert modular groups over arbitrary totally real number fields. An implementation of the algorithm is available to download from [20]. The exposition is self-contained and sufficient details are given for the reader to understand how it works and implement their own version if desired. [ABSTRACT FROM AUTHOR]

Path planning is an NP-hard problem that is aimed to satisfy multi-constraint optimization requirements. In autonomous robotics applications, path planning together with collision avoidance presents a challenging task. It necessitates the generation of possible search directions from a designated point to a fixed varying destination location satisfying spatial constraints. This paper presents a framework for the design of an intelligent multi-objective robotic path planning algorithm. The algorithm relies on the generation of way-points by hybridizing two meta-heuristics techniques, namely Grey Wolf Algorithm (GWO) and Particle Swarm Optimization (PSO). A frequency-based modification in GWO search operators is introduced to fasten the search process. An improvised search strategy is employed for collision detection and avoidance, which converts non-desired points into the desired point. Sensors are deployed around the robot vicinity for search optimization. Mutation operators are then introduced to improve path length by smoothing out the trajectory. The proposed algorithm's effectivity is then validated through extensive simulations, in which different condition environments are simulated. To validate the effectiveness of the proposed methodology, the results are compared with contemporary algorithms namely Minimum Angle Artificial Bee Colony (MAABC) algorithms, Hybrid Cuckoo Search-Bat Algorithm (BA-CSA), Bacterial Bolony (BC) and Genetic Algorithm (GA) algorithms. The results conclusively demonstrated that the proposed algorithm ensures effective performance in path smoothness and safety under a wide range of conditions. • A novel intelligent multi-objective framework for robotic path planning algorithm. • A hybridizing two meta-heuristics techniques to solve the path planning. • An improvised search strategy is employed for collision detection and avoidance. • The proposed algorithm's effectively validated through extensive simulations. [ABSTRACT FROM AUTHOR]

Communication overhead is the key challenge for distributed training. Gradient compression is a widely used approach to reduce communication traffic. When combined with a parallel communication mechanism method like pipeline, gradient compression technique can greatly alleviate the impact of communication overhead. However, there exist two problems of gradient compression technique to be solved. Firstly, gradient compression brings in extra computation cost, which will delay the next training iteration. Secondly, gradient compression usually leads to a decrease in convergence accuracy. In this paper, we combine parallel mechanism with gradient quantization and periodic full-gradient compensation, and propose a new distributed optimization method named CP-SGD, which can hide the overhead of gradient compression, overlap part of the communication and obtain high convergence accuracy. The local update operation in CP-SGD allows the next iteration to be launched quickly without waiting for the completion of gradient compression and the current communication process. Besides, the accuracy loss caused by gradient compression is solved by k-step correction method introduced in CP-SGD, which provides a gradient correction every k iterations. We prove that CP-SGD has a convergence guarantee and it achieves at least O (1 K + 1 K) convergence rate, where K is the number of iterations. We conduct extensive experiments on MXNet to verify the convergence properties and scaling performance of CP-SGD. Experimental results on a 32-GPU cluster show that convergence accuracy of CP-SGD is close to or even slightly better than that of S-SGD, and its end-to-end time is 30% less than 2-bit gradient compression under a 56Gbps bandwidth environment. In addition, we analyze the performance of CP-SGD when training on 8, 16 and 32 GPUs. It is found that CP-SGD is suitable for most compression-supported update algorithms, and its scalability is approximately linear. • CP-SGD: Distributed Stochastic Gradient Descent with Compression and Periodic Compensation. • CP-SGD help distributed deep learning train with high-accuracy and friendly-communication simultaneously. • Combining the advantages of parallel mechanism and gradient compression. • K-step correction technique makes CP-SGD achieve codesign optimizations and improve compression-based methods greatly. • CP-SGD suits most compression-supported update algorithms and gradient compression strategies. [ABSTRACT FROM AUTHOR]

Hard-thresholding-based algorithms have seen various advantages for sparse optimization in controlling the sparsity and allowing for fast computation. Recent research shows that when techniques of the Newton-type methods are integrated, their numerical performance can be improved surprisingly. This paper develops a gradient projection Newton pursuit algorithm that mainly adopts the hard-thresholding operator and employs the Newton pursuit only when certain conditions are satisfied. The proposed algorithm is capable of converging globally and quadratically under the standard assumptions. When it comes to compressive sensing problems, the imposed assumptions are much weaker than those for many state-of-the-art algorithms. Moreover, extensive numerical experiments have demonstrated its high performance in comparison with the other leading solvers. [ABSTRACT FROM AUTHOR]

In the Graph bipartization (or Odd Cycle Transversal) problem, the objective is to decide whether a given graph G can be made bipartite by the deletion of k vertices for some given k. The parameterized complexity of Odd Cycle Transversal was resolved in the breakthrough paper of Reed, Smith and Vetta [Operations Research Letters, 2004], who developed an algorithm running in time O (3 k k m n). The question of improving the dependence on the input size to linear, which was another long standing open problem in the area, was resolved by Iwata et al. [SICOMP 2016] and Ramanujan and Saurabh [TALG 2017], who presented O (4 k (m + n)) and 4 k k O (1) (m + n) algorithms respectively. In this paper, we obtain a faster algorithm that runs in time 3 k k O (1) (m + n) and hence preserves the linear dependence on the input size while nearly matching the dependence on k incurred by the algorithm of Reed, Smith and Vetta. [ABSTRACT FROM AUTHOR]

It was recently shown that on a large class of important Banach spaces there exist no linear methods which are able to approximate the Hilbert transform from samples of the given function. This implies that there is no linear algorithm for calculating the Hilbert transform which can be implemented on a digital computer and which converges for all functions from the corresponding Banach spaces. The present paper develops a much more general framework which also includes non-linear approximation methods. All algorithms within this framework have only to satisfy an axiom which guarantees the computability of the algorithm based on given samples of the function. The paper investigates whether there exists an algorithm within this general framework which converges to the Hilbert transform for all functions in these Banach spaces. It is shown that non-linear methods give actually no improvement over linear methods. Moreover, the paper discusses some consequences regarding the Turing computability of the Hilbert transform and the existence of computational bases in Banach spaces. [ABSTRACT FROM AUTHOR]

[Display omitted] • We present an improved algorithm (TOPS-2) for the design of optimized pulse sequence that can cover a wide range of chemical shifts. • The evolution of the Bloch equation is approximated as a sequence of small constant flip angle pulses with varying phases and constant amplitude. • Closed form optimal solutions of piecewise constant phases are obtained by incorporating linear and quadratic terms in the propagators. • Experimental validation is provided for TOPS excitation, inversion and TOCSY. This paper presents an improved iterative algorithm (TOPS-2) for the design of broadband inversion, excitation and coherent transfer mixing sequence (TOCSY) pulses. The evolution of the Bloch vector is presented as a sequence of small constant flip angle pulses with varying phases and constant amplitude. This paper describes an improved algorithm for iterative optimization of piece-wise constant phases as we incorporate the quadratic terms in the propagators. In our iterative optimization we obtain a closed-form expression for each phase, and these phases are optimized sequentially using the new improved algorithm. This paper compares the simulation results of the TOPS vs TOPS-2 and shows that TOPS-2 perform better. Experimental validation of excitation and inversion TOPS-2 pulse sequence is performed with. 5 % H 2 O in 99.5 % D 2 O, and experimental validation of TOPS-2 mixing (TOCSY) pulse sequence is done with 0.1 % of Ethylbenzene (EB) in CDCl 3 solvent. [ABSTRACT FROM AUTHOR]

For a simply connected connected simple algebraic group G , a cell B w 0 − = B − ∩ U w 0 ‾ U is a geometric crystal with a positive structure θ i − : (C ×) l (w 0) → B w 0 −. Applying the tropicalization functor to a rational function Φ B K h = ∑ i ∈ I Δ w 0 Λ i , s i Λ i called the half decoration on B w 0 − , one can realize the crystal B (∞) in Z l (w 0). By computing Φ B K h , we get an explicit form of B (∞) in Z l (w 0). In this paper, we give an algorithm to compute Δ w 0 Λ i , s i Λ i ∘ θ i − explicitly for i ∈ I such that V (Λ i) is a minuscule representation of g = Lie (G). In particular, the algorithm works for all i ∈ I if g is of type A n. The algorithm computes a directed graph DG , called a decoration graph , whose vertices are labelled by all monomials in Δ w 0 Λ i , s i Λ i ∘ θ i − (t 1 , ⋯ , t l (w 0)). The decoration graph has some properties similar to crystal graphs of minuscule representations. We also verify that the algorithm works in some other cases, for example, the case g is of type G 2 though V (Λ i) is non-minuscule. [ABSTRACT FROM AUTHOR]

• A parallel scalable DBSCAN algorithm which outperforms other implementations. • Optimizations for data partitioning, spatial indexing, and cluster merging. • Exploiting hybrid parallelization to take advantage of modern HPC architectures. • Demonstrating accuracy, performance and scalability of our algorithm. Dbscan is a density-based clustering algorithm which is well known for its ability to discover clusters of arbitrary shape as well as to distinguish noise. As it is computationally expensive for large datasets, research studies on the parallelization of Dbscan have been received a considerable amount of attention. In this paper we present an exact, efficient and scalable parallel Dbscan algorithm which we call Hy-Dbscan. It employs three major techniques to enable scalable data clustering on distributed-memory computers i) a modified kd-tree for domain decomposition, ii) a spatial indexing approach based on grid and inference, and iii) a cluster merging scheme based on distributed Rem's Union-Find algorithm. Moreover, Hy-Dbscan exploits process level and thread level parallelization. In experiments, we have demonstrated performance and scalability using two scientific datasets on up to 2048 cores of a distributed-memory computer. Through extensive evaluation, we show that Hy-Dbscan significantly outperforms previous state-of-the-art Dbscan implementations. [ABSTRACT FROM AUTHOR]

Protein–protein interactions (PPIs) are crucial for various biological processes, and predicting PPIs is a major challenge. To solve this issue, the most common method is link prediction. Currently, the link prediction methods based on network Paths of Length Three (L3) have been proven to be highly effective. In this paper, we propose a novel link prediction algorithm, named SMS, which is based on L3 and protein similarities. We first design a mixed similarity that combines the topological structure and attribute features of nodes. Then, we compute the predicted value by summing the product of all similarities along the L3. Furthermore, we propose the Max Similarity Multiplied Similarity (maxSMS) algorithm from the perspective of maximum impact. Our computational prediction results show that on six datasets, including S. cerevisiae, H. sapiens, and others, the maxSMS algorithm improves the precision of the top 500, area under the precision–recall curve, and normalized discounted cumulative gain by an average of 26.99%, 53.67%, and 6.7%, respectively, compared to other optimal methods. [Display omitted] • A mixed similarity combining sequence and topological structure is introduced. • A link prediction algorithm based on complementarity and similarity is proposed. • The proposed method performs better than existing L3, Sim and other methods. [ABSTRACT FROM AUTHOR]

In recent years there has been increased use of machine learning (ML) techniques within mathematics, including symbolic computation where it may be applied safely to optimise or select algorithms. This paper explores whether using explainable AI (XAI) techniques on such ML models can offer new insight for symbolic computation, inspiring new implementations within computer algebra systems that do not directly call upon AI tools. We present a case study on the use of ML to select the variable ordering for cylindrical algebraic decomposition. It has already been demonstrated that ML can make the choice well, but here we show how the SHAP tool for explainability can be used to inform new heuristics of a size and complexity similar to those human-designed heuristics currently commonly used in symbolic computation. [ABSTRACT FROM AUTHOR]

Online learning is an efficient approach in machine learning and statistics, which iteratively updates models upon the observation of a sequence of training examples. A representative online learning algorithm is the online gradient descent, which has found wide applications due to its low complexity and scalability to large datasets. Kernel-based learning methods have been proven to be quite successful in dealing with nonlinearity in the data and multivariate optimization. In this paper we present a class of kernel-based online gradient descent algorithm for addressing regression problems, which generates sparse estimators in an iterative way to reduce the algorithmic complexity for training streaming datasets and model selection in large-scale learning scenarios. In the setting of support vector regression (SVR), we design the sparse online learning algorithm by introducing a sequence of insensitive distance-based loss functions. We prove consistency and error bounds quantifying the generalization performance of such algorithms under mild conditions. The theoretical results demonstrate the interplay between statistical accuracy and sparsity property during learning processes. We show that the insensitive parameter plays a crucial role in providing sparsity as well as fast convergence rates. The numerical experiments also support our theoretical results. [ABSTRACT FROM AUTHOR]

The selective delayless subband structure stands out as a promising algorithmic choice for the multi-channel active control of vehicle interior noise, particularly in the context of road noise. This type of algorithm reduces the eigenvalue spread of the autocorrelation matrix of the signal by decomposing the signal into subbands, and the desired subbands are activated selectively, thus achieving a significant performance improvement while consuming less computational resources compared with the traditional fullband algorithms. Nevertheless, the effectiveness of the subband algorithm appears to be closely tied to the configuration of the primary disturbance signal. In cases where the primary disturbance signal encompasses both broadband and tonal components, the performance advantage of the subband algorithm becomes constrained. In this paper, we conduct a thorough comparative analysis of two extensively employed subband algorithms, namely the Morgan and the Milani methods, through simulations employing data obtained from a multi-channel active noise control (ANC) headrest system. The results indicate that the Morgan method outperforms the Milani method when configured optimally. Subsequently, we propose an enhanced version of the subband algorithm based on the Morgan method. The enhanced algorithm incorporates an additional sinusoidal noise canceller (SNC) subsystem and a narrowband active noise control (NANC) subsystem based on local secondary path modeling to address tonal components, while the selective subband structure is employed for controlling broadband components. In addition, the computational complexity of the algorithm is analyzed. The effectiveness of the proposed algorithm is validated through numerous simulations and the ANC tests conducted on an actual vehicle utilizing the multi-channel ANC headrest system. The performance of the proposed algorithm surpasses that of traditional selective subband and fullband algorithms, and balanced binaural noise reduction is achieved. [ABSTRACT FROM AUTHOR]

DNA 4 mC plays a crucial role in the genetic expression process of organisms. However, existing deep learning algorithms have shortcomings in the ability to represent DNA sequence features. In this paper, we propose a 4 mC site identification algorithm, DNABert-4mC, based on a fusion of the pruned pre-training DNABert-Pruning model and artificial feature encoding to identify 4 mC sites. The algorithm prunes and compresses the DNABert model, resulting in the pruned pre-training model DNABert-Pruning. This model reduces the number of parameters and removes redundancy from output features, yielding more precise feature representations while upholding accuracy.Simultaneously, the algorithm constructs an artificial feature encoding module to assist the DNABert-Pruning model in feature representation, effectively supplementing the information that is missing from the pre-trained features. The algorithm also introduces the AFF-4mC fusion strategy, which combines artificial feature encoding with the DNABert-Pruning model, to improve the feature representation capability of DNA sequences in multi-semantic spaces and better extract 4 mC sites and the distribution of nucleotide importance within the sequence. In experiments on six independent test sets, the DNABert-4mC algorithm achieved an average AUC value of 93.81%, outperforming seven other advanced algorithms with improvements of 2.05%, 5.02%, 11.32%, 5.90%, 12.02%, 2.42% and 2.34%, respectively. [Display omitted] • Train a new pruning pretraining model on DNA sequences to extract feature information. • The introduction of manually assisted features has expanded the search space for sequence feature. • Attention fusion strategy better promotes the fusion output of features from different dimensions. • The complementary nature of machine features and manual features better fits the target features. [ABSTRACT FROM AUTHOR]

This paper introduces a novel parameter related to bearing degradation, namely the Equivalent Damaged Volume (EDV). An algorithm capable of extracting EDV values from experimental data is detailed. To this end, the proposed technique relies on the comparison between experimental and numerical signals. The former are the result of an extensive campaign of run-to-failure tests performed on a dedicated test rig. On the other hand, the latter are obtained by means of a lumped parameter model that accounts for the angular extent and the depth of either localized or extended defects. The potential of this novel technique is demonstrated by exploiting the values obtained by the algorithm as inputs for a prognostic model. In particular, the developed model aims at predicting the time until a certain threshold on the equivalent damaged volume is crossed, regardless of the applied load and the shaft rotation speed. The advantages and downsides introduced by the proposed approach are thoroughly discussed by providing examples based on real degradation histories. [ABSTRACT FROM AUTHOR]

• A near-field weighted subspace fitting algorithm is proposed for ultrasonic guided wave multi-damage localization. • A near-field multi-dimensional solution search algorithm based on a niche particle swarm optimization is proposed, which effectively improves the efficiency of damage localization. • Algorithm performance comparison, finite element simulation, real point damage and slot damage experiments verify the effectiveness of the proposed method. The ultrasonic guided wave-based method for multi-damage localization has been widely proposed. However, the precision of this method is directly correlated with both the quantity of sensors employed and the intricacy of the implementation process. This relationship poses a challenge in striking a balance between the accuracy and efficiency. To improve the computational efficiency under the premise of ensuring the accuracy of multi-damage localization, this paper proposes a near-field weighted subspace fitting algorithm based on niche-particle swarm optimization. Firstly, the fitting relationship between the signal subspace of the diffraction wave and the array steering vector is established under the uniform linear array. Secondly, a multi-dimensional solution space search algorithm based on niche-particle swarm optimization is proposed to improve the search efficiency of damage. Finally, the algorithm is verified by performance comparison, finite element simulation and experiment. The results show that compared with the same type of method, the algorithm improves the computational efficiency by nearly threefold under the identifiable multi-damage conditions. Additionally, the angle error is 1 ∼ 6°, and the distance error is 1 ∼ 20 mm. [ABSTRACT FROM AUTHOR]

The Chow ring of the moduli space of stable marked curves is generated by Keel's divisor classes. The top graded part of this Chow ring is isomorphic to the integers, generated by the class of a single point. In this paper, we give an equivalent graphical characterization on the monomials in this Chow ring, as well as the characterization on the algebraic reduction on such monomials. Moreover, we provide an algorithm for computing the intersection degree of tuples of Keel's divisor classes — we call it the forest algorithm; the complexity of which is O (n 3) in the worst case, where n refers to the number of marks on the stable curves in the ambient moduli space. Last but not least, we introduce three identities on multinomial coefficients which naturally came into play, showing that they are all equivalent to the correctness of the base case of the forest algorithm. [ABSTRACT FROM AUTHOR]

In this paper we study the Shor relaxation of quadratic programs by fixing a feasible set and considering the space of objective functions for which the Shor relaxation is exact. We first give conditions under which this region is invariant under the choice of generators defining the feasible set. We then describe this region when the feasible set is invariant under the action of a subgroup of the general linear group. We conclude by applying these results to quadratic binary programs. We give an explicit description of objective functions where the Shor relaxation is exact and use this knowledge to design an algorithm that produces candidate solutions for binary quadratic programs. [ABSTRACT FROM AUTHOR]

Algorithmic stability is a fundamental concept in statistical learning theory to understand the generalization behavior of optimization algorithms. Existing high-probability bounds are developed for the generalization gap as measured by function values and require the algorithm to be uniformly stable. In this paper, we introduce a novel stability measure called pointwise uniform stability by considering the sensitivity of the algorithm with respect to the perturbation of each training example. We show this weaker pointwise uniform stability guarantees almost optimal bounds, and gives the first high-probability bound for the generalization gap as measured by gradients. Sharper bounds are given for strongly convex and smooth problems. We further apply our general result to derive improved generalization bounds for stochastic gradient descent. As a byproduct, we develop concentration inequalities for a summation of weakly-dependent vector-valued random variables. [ABSTRACT FROM AUTHOR]

A binocular camera composed of colour and depth cameras is an accurate and inexpensive tool for recognising fruit trees to plan spraying paths. For this purpose, however, the accurate visual registration of the depth and colour cameras is a problem that must be solved. This paper proposes a local feature point extraction (LFPE) algorithm for depth-colour image registration, which automatically extracts the feature points of local regions in the colour and depth images for registration. First, the binarised colour and depth images are divided into local regions after edge extraction, and the regions in which the edge features match at several pixels between images are selected. Then, these regions are again divided into smaller regions to detect local extrema of the pixels as feature points. Finally, the matching feature points are calculated based on the Euclidean distance and are used to optimise the affine transformation matrix. To verify the accuracy and effectiveness of the algorithm, it is compared with the FAST, SURF and BRISK algorithms. The experimental results show that the accuracy of the proposed LFPE algorithm is 1.6 times that of BRISK, 3.5 times that of FAST and 40.1 times that of SURF. Therefore, it is more suitable for registration between depth and colour images. • Proposed a depth-colour image registration method for orchard precision spraying. • A local feature point extraction (LFPE) algorithm is proposed to match images. • The registration accuracy of LFPE is much better than other similar algorithms. [ABSTRACT FROM AUTHOR]

The vigorous development and the increasing popularity of cloud computing highlight the necessity of reducing data center energy consumption and the environmental impact of carbon dioxide emissions. For geographically distributed data centers, cloud servers are connected to the conventional power grid and in addition they are supported by an attached renewable energy source. Since the carbon footprint rate of energy consumption has dynamic differences in space, reducing energy consumption does not mean decrease carbon emission, which indicates that energy consumption and carbon footprint need to be synergistically optimized. In this paper, an energy and carbon-aware algorithm for virtual machine placement is proposed. The goal is to obtain a virtual machine allocation scheme that aims to achieve the trade-off between energy consumption and carbon emissions by improving renewable energy utilization. The experimental results show that the proposed approach is more energy-efficient and greener, which can also maximize the renewable energy utilization with 73.11% while ensuring the SLA violation with 0.2% in comparison to the baseline algorithms. • Propose a novel energy-aware VM placement approach in cloud data centers. • Introduce renewable energy for managing energy consumption and carbon footprint. • Design renewable energy generation prediction method based on EEMD and TCN. • Demonstrate the superiority of the proposed algorithm with five baseline algorithms. [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]

A basic problem in transcendental number theory is to determine the arithmetic properties of values of special functions. Many special functions, such as Bessel functions and certain hypergeometric functions, are E -functions which are a natural generalization of the exponential function and satisfy certain linear differential equations. In this case, there exists an algorithm which determines if f (α) is transcendental or algebraic if f (z) is an E -function and α ∈ Q ‾ ⁎ is a non-zero algebraic number. In this paper, we consider the analogous question when f (z) satisfies an integral equation, in particular, a Fredholm integral equation of the first or second kind where the kernel and forcing term satisfy strong arithmetic properties. We show that in both periodic and non-periodic cases, there exists no algorithm to determine if f (0) ∈ Q is rational. Our results are an application of the undecidability of the Generalized Collatz Problem due to Conway [6]. [ABSTRACT FROM AUTHOR]

• Our algorithm is more efficient, has less communication overhead, and has greater throughput than the original PBFT algorithm. • We propose a Vehicle - Service Provider - Roadside Unit architecture to ensure the orderliness and safety of vehicles. • We propose an identity authentication scheme based on blockchain. • Experimental results demonstrate that our solution is better than PBFT, G-PBFT and CPBFT. As an application of Internet of Things (IoT) technology, the Internet of Vehicles (IoV) faces two main security issues: (1) the central server of the IoV may not be powerful enough to support the centralized authentication of the rapidly increasing connected vehicles, (2) the IoV itself may not be robust enough to single-node attacks. To address these issues, in this paper, we propose SG-PBFT (Score Grouping-PBFT), a secure and efficient distributed consensus algorithm for blockchain applications in the IoV. The distributed structure can reduce the pressure on the central server and decrease the risk of single-node attacks. The SG-PBFT consensus algorithm improves the traditional practical Byzantine fault tolerance (PBFT) consensus algorithm by optimizing the PBFT consensus process and using a score grouping mechanism to achieve a higher consensus efficiency. The experimental results show that the method can greatly improve the consistency efficiency and effectively prevent single-node attacks. Specifically, when the number of consensus nodes reaches 1000, the consensus time of our algorithm is only about 27% of what is required for the state-of-the-art PBFT consensus algorithm. Our proposed SG-PBFT algorithm is versatile and can be used in other application scenarios which require high consensus efficiency. [ABSTRACT FROM AUTHOR]

The median of a set of vertices P of a graph G is the set of all vertices x of G minimizing the sum of distances from x to all vertices of P. In this paper, we present a linear time algorithm to compute medians in median graphs. We also present a linear time algorithm to compute medians in the associated ℓ 1 -cube complexes. Our algorithm is based on the majority rule characterization of medians in median graphs and on a fast computation of parallelism classes of edges (Θ-classes) via Lexicographic Breadth First Search (LexBFS). We show that any LexBFS ordering of the vertices of a median graph satisfies the following fellow traveler property : the parents of any two adjacent vertices are also adjacent. Using the fast computation of the Θ-classes, we also compute the Wiener index (total distance) in linear time and the distance matrix in optimal quadratic time. [ABSTRACT FROM AUTHOR]

An increasing amount of malicious code causes harm on the internet by threatening user privacy as one of the primary sources of network security vulnerabilities. The detection of malicious code is becoming increasingly crucial, and current methods of detection require much improvement. This paper proposes a method to advance the detection of malicious code using convolutional neural networks (CNNs) and intelligence algorithm. The CNNs are used to identify and classify grayscale images converted from executable files of malicious code. Non-dominated Sorting Genetic Algorithm II (NSGA-II) is then employed to deal with the data imbalance of malware families. A series of experiments are designed for malware image data from Vision Research Lab. The experimental results demonstrate that the proposed method is effective, maintaining higher accuracy and less loss. • A technique for converting a malware binary to an image was introduced. • In this paper, a method based on CNN is used to identify and classify the malicious codes. • An effective data equilibrium approach based on the NSGA-II was designed. • The proposed method was demonstrated through the extensive experiments. [ABSTRACT FROM AUTHOR]

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]

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

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]

Highlights • In this paper we propose a data segmentation method using robust multi model fitting and hypergraph clustering. • We propose a novel MCMC method that samples effectively from the distribution of hyperedges of a hypergraph. • We propose an effective mechanism to include the structure size parameter in data modeling and use an estimate of the parameter to improve the segmentation outcome. • The proposed method is compared with the state of the art methods and it is shown to perform favorably for different visual data segmentation scenarios. Abstract This paper approaches the problem of geometric multi-model fitting as a data segmentation problem. The proposed solution is based on a sequence of sampling hyperedges from a hypergraph, model selection and hypergraph clustering steps. We developed a sampling method that significantly facilitates solving the segmentation problem using a new form of the Markov-Chain-Monte-Carlo (MCMC) method to effectively sample from hyperedge distribution. To sample from this distribution effectively, our proposed Markov Chain includes new ways of long and short jumps to perform exploration and exploitation of all structures. To enhance the quality of samples, a greedy algorithm is used to exploit nearby structure based on the minimization of the Least k th Order Statistics cost function. Unlike common sampling methods, ours does not require any specific prior knowledge about the distribution of models. The output set of samples leads to a clustering solution by which the final model parameters for each segment are obtained. The method competes favorably with the state-of-the-art both in terms of computation power and segmentation accuracy. [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]

Several extrapolation strategies have been proposed in the literature to accelerate the EM algorithm, with varying degrees of success. One advantage of extrapolation methods is their ease of implementation, as they only require working with the EM iterations and do not need auxiliary quantities, such as gradient and Hessian. In this paper, we introduce a new family of iterative schemes based on vector extrapolation methods. We also construct and numerically test a randomly relaxed version of the scheme. Our results demonstrate that these new strategies can significantly and stably accelerate the convergence of the EM algorithm compared to existing methods. Moreover, these strategies are highly versatile as they can accelerate any linearly convergent fixed point iteration, including EM-type algorithms. Finally, we provide statistical modeling experiments at the end of the paper to demonstrate the applicability and interest of these convergence acceleration schemes, whether applied to the EM algorithm or one of its variants. [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]

In algebraic geometry, the Frobenius map (or called Frobenius action , or Frobenius operator) F ⁎ on cohomology groups plays an important role in the classification of algebraic varieties over a field of positive characteristic. In particular, representation matrices for F ⁎ give rise to many important invariants such as p -rank and a -number. Several methods for computing representation matrices for F ⁎ have been proposed for specific curves. In this paper, we present an algorithm to compute representation matrices for F ⁎ of general projective schemes over a perfect field of positive characteristic. We also propose an efficient algorithm specific to complete intersections; it requires to compute only certain coefficients in a power of a multivariate polynomial. Our algorithms shall derive fruitful applications such as computing Hasse-Witt matrices, and enumerating superspecial curves. In particular, the second algorithm for complete intersections provides a useful tool to judge the superspeciality of an algebraic curve, which is a key ingredient to prove main results in Kudo and Harashita (2017a,b, 2020) on the enumeration of superspecial genus-4 curves. [ABSTRACT FROM AUTHOR]

Consider an action of a connected solvable group G on an affine variety X. This paper presents an algorithm that constructs a semi-invariant f ∈ K [ X ] = : R and computes the invariant ring (R f) G together with a presentation. The morphism X f → Spec ((R f) G) obtained from the algorithm is a universal geometric quotient. In fact, it is even better than that: a so-called excellent quotient. If R is a polynomial ring, the algorithm requires no Gröbner basis computations. If R is a complete intersection, then so is (R f) G. [ABSTRACT FROM AUTHOR]

Read-only memory (ROM) model is a classical model of computation to study time-space tradeoffs of algorithms. More recently, several graph algorithms have been studied under ROM model. In this paper, we study graph algorithms under two different relaxations of ROM model, referred to as the implicit and rotate models, and show that these simple relaxations allow us to implement fundamental graph search methods like BFS and DFS more space efficiently than in ROM model. All our algorithms are simple but quite subtle, and we believe that these models are practical enough to spur interest for other graph problems in these models. [ABSTRACT FROM AUTHOR]

Satisfiability of word equations problem is: Given two sequences consisting of letters and variables decide whether there is a substitution for the variables that turns this equation into true equality. The exact computational complexity of this problem remains unknown, with the best lower and upper bounds being, respectively, NP and PSPACE. Recently, the novel technique of recompression was applied to this problem, simplifying the known proofs and lowering the space complexity to (non-deterministic) O (n log ⁡ n). In this paper we show that satisfiability of word equations is in non-deterministic linear space, thus the language of satisfiable word equations is context-sensitive. We use the known recompression-based algorithm and additionally employ Huffman coding for letters. The proof, however, uses analysis of how the fragments of the equation depend on each other as well as a new strategy for non-deterministic choices of the algorithm. [ABSTRACT FROM AUTHOR]