Search

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

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]

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]

It is increasingly realized that taking stochastic effects into account is important in order to study biological cells. However, the corresponding mathematical formulation, the chemical master equation (CME), suffers from the curse of dimensionality and thus solving it directly is not feasible for most realistic problems. In this paper we propose a dynamical low-rank algorithm for the CME that reduces the dimensionality of the problem by dividing the reaction network into partitions. Only reactions that cross partitions are subject to an approximation error (everything else is computed exactly). This approach, compared to the commonly used stochastic simulation algorithm (SSA, a Monte Carlo method), has the advantage that it is completely noise-free. This is particularly important if one is interested in resolving the tails of the probability distribution. We show that in some cases (e.g. for the lambda phage) the proposed method can drastically reduce memory consumption and run time and provide better accuracy than SSA. • We propose a low-rank algorithm that does not rely on single orbital basis functions. • The proposed approach is better suited for biological/chemical reaction networks. • We demonstrate better accuracy and improved efficiency compared to SSA for some problems. • The proposed complexity reduction algorithm is noise free (in contrast to SSA). • We demonstrate that our algorithm accurately resolves the tails of the distribution (in contrast to SSA). [ABSTRACT FROM AUTHOR]

It has been shown that any nonblocking algorithm for work-stealing in the standard asynchronous shared memory model of computation must use expensive Read-After-Write synchronization patterns or atomic Read-Modify-Write instructions. Algorithms for relaxations of work-stealing have been proposed, which only partially avoid this impossibility result. In restricted models of computation, work-stealing algorithms have been designed that avoid Read-After-Write patterns and atomic Read-Modify-Write instructions. This paper considers work-stealing with multiplicity , a relaxation in which every task is taken by at least one process, and any process can take any task at most once. We study two variants of the relaxation, for each variant designing a Read / Write wait-free algorithm in the standard asynchronous shared memory model. The two algorithms are devoid of Read-After-Write synchronization patterns in all their operations, and additionally, the algorithm for the second variant has constant step complexity and is fence-free. Namely, no specific ordering among the algorithm's instructions is required beyond what is implied by data dependence. To our knowledge, these are the first algorithms for relaxations of work-stealing possessing all these properties. The algorithms are also solutions to relaxed versions of single-enqueuer multi-dequeuer queues. The theoretical results are complemented with an experimental evaluation showing that the benefits of relaxed work-stealing vary depending on the application, concretely on the complexity of the work associated with each task. • We present two asynchronous work-stealing algorithms with relaxation, work-stealing with multiplicity and weak-multiplicity. • In the first one, tasks are taken by at least one operation and if taken by several operations, they must be pairwise concurrent. • In the second one, Take/Steal operations extracting the same task may not be concurrent, however, each process extracts tasks at most once. • The algorithms are wait-free, read/write, and devoid of read-after-write synchronization patterns. • The proposed algorithms outperform standard work-stealing algorithms and exhibit similar or better performance than known relaxed algorithms in some practical settings. [ABSTRACT FROM AUTHOR]

Operators from various industries have been pushing the adoption of wireless sensing nodes for industrial monitoring, and such efforts have produced sizeable condition monitoring datasets that can be used to build diagnosis algorithms capable of warning maintenance engineers of impending failure or identifying current system health conditions. However, single operators may not have sufficiently large fleets of systems or component units to collect sufficient data to develop data-driven algorithms. One potential solution to overcome the challenge of having limited representative datasets is to merge datasets from multiple operators with the same type of assets. However, directly sharing data across the company's borders yields privacy concerns. Federated learning (FL) has emerged as a promising solution to leverage datasets from multiple operators to train a decentralized asset fault diagnosis model while maintaining data confidentiality. However, the performance of traditional FL algorithms degrades when local clients' datasets are heterogeneous. The dataset heterogeneity is particularly prevalent in fault diagnosis applications due to the high diversity of operating conditions and system configurations. To address this challenge, this paper proposes a novel clustering-based FL algorithm where clients are clustered based on their dataset similarity. Estimating dataset similarity between clients without explicitly sharing data is achieved by training probabilistic deep learning models and having each client examine the predictive uncertainty of the other clients' models on its local dataset. Clients are then clustered for FL based on relative prediction accuracy and uncertainty. Experiments on three bearing fault datasets, two publicly available and one newly collected for this work, show that our algorithm significantly outperforms FedAvg and a cosine similarity-based algorithm by 5.1% and 30.7% on average over the three datasets. Further, using a probabilistic classification model has the additional advantage of accurately quantifying its predictive uncertainty, which we show it does exceptionally well. [ABSTRACT FROM AUTHOR]

Steepest descent methods combining complex contour deformation with numerical quadrature provide an efficient and accurate approach for the evaluation of highly oscillatory integrals. However, unless the phase function governing the oscillation is particularly simple, their application requires a significant amount of a priori analysis and expert user input, to determine the appropriate contour deformation, and to deal with the non-uniformity in the accuracy of standard quadrature techniques associated with the coalescence of stationary points (saddle points) with each other, or with the endpoints of the original integration contour. In this paper we present a novel algorithm for the numerical evaluation of oscillatory integrals with general polynomial phase functions, which automates the contour deformation process and avoids the difficulties typically encountered with coalescing stationary points and endpoints. The inputs to the algorithm are simply the phase and amplitude functions, the endpoints and orientation of the original integration contour, and a small number of numerical parameters. By a series of numerical experiments we demonstrate that the algorithm is accurate and efficient over a large range of frequencies, even for examples with a large number of coalescing stationary points and with endpoints at infinity. As a particular application, we use our algorithm to evaluate cuspoid canonical integrals from scattering theory. A Matlab implementation of the algorithm is made available and is called PathFinder. • An algorithm for the evaluation of oscillatory integrals with polynomial phase. • The algorithm automates the numerical steepest descent method. • Our implementation is robust and efficient across all frequencies. [ABSTRACT FROM AUTHOR]

We develop the first algorithm for computing rational solutions of scalar integro-differential equations with polynomial coefficients. It starts by finding the possible poles of a rational solution. Then, bounding the order of each pole and solving an algebraic linear system, we compute the singular part of rational solutions at each possible pole. Finally, using partial fraction decomposition, the polynomial part of rational solutions is obtained by computing polynomial solutions of a non-homogeneous scalar integro-differential equation with a polynomial right-hand side. The paper is illustrated by examples where the computations are done with our Maple implementation. [ABSTRACT FROM AUTHOR]

Mixed trigonometric-polynomials (MTPs) are functions of the form f (x , sin ⁡ x , cos ⁡ x) where f is a trivariate polynomial with rational coefficients, and the argument x ranges over the reals. In this paper, an algorithm "isolating" all the real roots of an MTP is provided and implemented. It automatically divides the real roots into two parts: one consists of finitely many roots in an interval [ μ − , μ + ] while the other consists of countably many roots in R ﹨ [ μ − , μ + ]. For the roots in [ μ − , μ + ] , the algorithm returns isolating intervals and corresponding multiplicities while for those greater than μ + , it returns finitely many mutually disjoint small intervals I i ⊂ [ − π , π ] , integers c i > 0 and multisets of root multiplicity { m j , i } j = 1 c i such that any root > μ + is in the set (∪ i ∪ k ∈ N (I i + 2 k π)) and any interval I i + 2 k π ⊂ (μ + , ∞) contains exactly c i distinct roots with multiplicities m 1 , i ,... , m c i , i , respectively. The efficiency of the algorithm is shown by experiments. The method used to isolate the roots in [ μ − , μ + ] is applicable to any other bounded interval as well. The algorithm takes advantages of the weak Fourier sequence technique and deals with the intervals period-by-period without scaling the coordinate so to keep the length of the sequence short. The new approaches can easily be modified to decide whether there is any root, or whether there are infinitely many roots in unbounded intervals of the form (− ∞ , a) or (a , ∞) with a ∈ Q. [ABSTRACT FROM AUTHOR]

Vehicle on-board monitoring methods use responses of running vehicles to identify track irregularity in real time. But the parameters of both the bridges and the vehicles in such processes may have a non-negligible degree of uncertainty or randomness that will inevitably lead to uncertainty in the track irregularity identification. Quantifying such uncertainty is a great challenge as the vehicle-bridge system (VBS) to be treated with is time-dependent and random. This paper proposes an on-board track irregularity identification algorithm that realizes an inverse random dynamic analysis of the VBS to quantify estimation uncertainty by using a Bayesian Kalman filter technology. The proposed algorithm utilizes sigma point sets to simulate the random parameters and the noises, and is therefore capable of implementing high-fidelity probability density propagation in the nonlinear state transfer and observation functions describing the VBS. The proposed algorithm is validated by numerical examples with various running states and parameter uncertainty levels. [ABSTRACT FROM AUTHOR]

The correlation filter based online tracking methods usually can achieve high real-time performance due to the leverage of the well-known FFT. However, they are also apt to generate the "corrupted training samples" in scenarios with complex background, which will trigger the model drift and deteriorate the tracking accuracy rapidly. The existing methods usually consider this problem from certain aspect and none of them has mined the potential of combining multiple formulas. In this paper, we propose the Output Constraint Transfer - Discriminative Scale Space Tracking (OCT-DSST) algorithm, which has taken full consideration of multiple channel feature, multiple filters, kernel trick, memory with incremental learning, and the self-supervision mechanism. We re-formulate the online tracking process by combining all formulas above in a unified framework. The so obtained adaptive learning rate can better exploit the feedback information coming from the intermediate tracking results, and effectively mitigate the corrupted sample problem. The experimental results on the OTB-50/100 and the VOT2016 datasets reveal that the proposed method is comparative to most state-of-the-arts algorithms, and can increase the accuracy by 2% and the success rate by 1.7%, compared to the traditional DSST method. [ABSTRACT FROM AUTHOR]

• An original classification of attacks on robust watermarks is proposed. • A review of watermarking schemes designed to counter targeted attacks is presented. • The main methods of countering targeted attacks are noted. • Promising research directions are discussed. Image watermarking is an effective and promising technology. Robust watermarks that are resistant to various attacks allow authors and owners of digital images to protect their rights to digital content, control its distribution and confirm its authenticity. Most of the modern algorithms for robust image watermarking aim to achieve resistance to a large number of different attacks. However, some authors develop algorithms designed to counter targeted attacks. The study of such schemes allows developers of watermarking algorithms to evaluate special means of counteracting various attacks, and then use them to create new robust schemes, both targeted and universal ones. In this paper, we present an overview of robust image watermarking schemes in terms of countering targeted attacks. We review the state-of-the-art in the field of attacking robust watermarks and propose a four-level classification of attacks that includes different levels of attack implementation, including an attacker's intent, characteristics of actions, the main target and an attack type. The proposed classification considers a watermark as an object of attack and summarizes various characteristics of attacks in a hierarchical manner. We analyze the means of countering common attacks such as image processing attacks, geometric attacks, print-scan and screen capture attacks, collusion attacks, and ambiguity attacks. Based on the results of our review, we highlight the most common methods of countering attacks and formulate promising areas of research in the field of methods for improving security of embedding schemes. [ABSTRACT FROM AUTHOR]

By a result of Latimer and MacDuffee, there are a finite number of equivalence classes of n × n matrices over F q [ T ] with minimum polynomial p (X) , where p is an n th degree polynomial, irreducible over F q [ T ]. In this paper, we develop an algorithm for finding a canonical representative of each matrix class, for p (X) = X 2 − Γ X − Δ ∈ F q [ T ] [ X ]. [ABSTRACT FROM AUTHOR]

We propose an easy-to-implement iterative method for resolving the implicit (or semi-implicit) schemes arising in solving reaction-diffusion (RD) type equations. We formulate the nonlinear time implicit scheme as a min-max saddle point problem and then apply the primal-dual hybrid gradient (PDHG) method. Suitable precondition matrices are applied to the PDHG method to accelerate the convergence of algorithms under different circumstances. Furthermore, our method is applicable to various discrete numerical schemes with high flexibility. From various numerical examples tested in this paper, the proposed method converges properly and can efficiently produce numerical solutions with sufficient accuracy. [ABSTRACT FROM AUTHOR]

The robustness of dynamical systems against external perturbations is crucial in engineering; however, it is often overlooked for the lack of methods for rapidly computing it. This paper proposes a novel algorithm for estimating the robustness of systems subject to time delay. More precisely, the algorithm iteratively estimates the so-called local integrity measure (LIM), that is, the radius of the largest hypersphere centered at the fixed point and located within its basin of attraction. Since time-delayed systems are infinite dimensional, initial conditions are restricted to a constrained type of initial functions. The semi-discretization method is used for rapidly simulating the dynamics of the systems, while trajectories are classified as converging or diverging using a subdivision of the reduced phase space into cells. The algorithm was tested on four different mechanical systems, and in all cases it very quickly provided an accurate estimation of the LIM. Moreover, it enabled the study of LIM trends in a multi-dimensional parameter space, which would have been unfeasible with alternative methods. This breakthrough in computational efficiency has important implications for engineering design, allowing for careful consideration of dynamical integrity and enhancing the safety and reliability of engineered systems, especially in the presence of time delays. • An algorithm for estimating the dynamical integrity of equilibria is developed. • The algorithm works for time-delayed dynamical systems. • The algorithm works iteratively, it is very quick and has no memory issues. • It enables one to consider dynamical integrity during engineering design. • Several case studies demonstrate the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

• A single-step recursive algorithm of non-viscous damping forces is developed. • Rectangle-impulse responses of kernel functions determine the algorithm parameters. • The algorithm is compatible with the solution schemes of time integration methods. • The compatible algorithm retains the characteristics of time integration methods. The non-viscous damping force features the convolution integral of the velocity and the kernel function, causing the difficulty of the solutions of the system equation of motion due to the nonlocal time dependence. In accordance with the linear time-invariant system theory in signal processing, this paper presents a single-step recursive algorithm of convolution integral for efficiently computing non-viscous damping forces. The algorithm parameters are effectively identified from the discrete responses of the kernel function to the rectangular unit impulse through digital filter technologies. The proposed algorithm is compatible with the solution schemes based on existing time integration methods, which handle the nonlocal dependence using internal recursive support vectors while leaving the order of the equation of motion unchanged. The central difference method, the Newmark- ß method, and the Bathe method are employed to illustrate the use of the algorithm, proving to retain the stability characteristics of time integration methods. The single and multiple DOF examples show that the simulated results based on the compatible solution schemes compare well with those built on other existing methods, verifying high accuracy and efficiency. The proposed algorithm thus extends the application range of existing time integration methods from the viscously damped system to the non-viscously damped one, fully demonstrating its generalizability. [ABSTRACT FROM AUTHOR]

Atomic Broadcast is an essential broadcast primitive as it ensures the consistency of distributed replicas. However, it is notoriously non-scalable. In this work, we introduce the Leaderless Hierarchical Atomic Broadcast (LHABcast) algorithm, which has two properties to improve scalability. First, it is a fully decentralized algorithm that does not rely on a sequencer/leader, which is often a significant bottleneck. Processes running LHABcast send messages with local sequence numbers and order messages received from other processes using timestamps inspired on Lamport's logical clocks. A process that receives the required set of timestamps can make a decision about the overall sequence of message delivery. Second, the algorithm is hierarchical: processes are organized on a vCube logical overlay network, which has several logarithmic properties and allows the construction of autonomous spanning trees. vCube also works as a failure detector, assuming crash faults and an asynchronous system model. In this paper, LHABcast is described, specified, and proven to be correct. Both simulation and experimental results are presented. A comparison with an all-to-all strategy shows that the number of messages sent by LHABcast is significantly lower in both fault-free and faulty scenarios. An implementation of LHABcast in Akka.io achieved up to 3.9 times higher throughput in fault-free scenarios than an implementation of the Raft-based Apache Ratis. • LHABcast is a fully decentralized leaderless algorithm broadcast algorithm. • LHABcast organizes processes on a vCube, which has several logarithmic properties. • LHABcast uses autonomic spanning trees rooted at the sender for message dissemination. • LHABcast is described with examples, and multiple properties are proved. • LHABcast was evaluated both with a Neko simulation and using the Java Akka framework. [ABSTRACT FROM AUTHOR]

Researchers have been involved for decades in search of an efficient skin detection method. However, current methods have not overcome the significant challenges of skin detection, such as variation of illumination, various skin tones of different ethnic groups, and many others. This research proposed a clustering and region-growing-based skin detection method to overcome these limitations. Together with significant insight, these methods result in a more effective algorithm. The insight concerns the capability to dynamically define the number of clusters in a collection of pixels organized as images. In Clustering for most problem domains, the number of clusters is fixed prior and does not perform effectively over a wide variety of data contents. Therefore, this research paper proposed a skin detection method that validated the above findings. The proposed method assigns the number of clusters based on image properties and ultimately allows freedom from manual thresholds or other manual operations. The dynamic determination of clustering outcomes allows for greater automation of skin detection when dealing with uncertain real-world conditions. • Human skin tone is uniform, and clustering is an efficient method to detect human skin. • CIELAB color space is better for separating illumination from the image. • A small number of significant objects can occupy most of the pixel in an image. • Pixel connectivity of an image can automatically decide the number of clusters. • Clustering performs efficiently in Human skin detection. [ABSTRACT FROM AUTHOR]

Domain Generalization (DG) model is an important tool to improve the robustness of person re-identification algorithm, but the domain gap makes it difficult to transfer knowledge cross-domain effectively. To solve the above problems, this paper proposes a generalization model based on a Meta-Bond Domain Alignment (M−BDA) model. To learn a generalizable model, a meta -learning strategy is introduced to simulate the training–testing process of the domain generalization. Then a bond-domain module is constructed in the training to align the source domain, which can reduce the domain gap between the source domain and the target domain, and facilitate the knowledge transfer. Finally, the bond-domain loss is counted on the feature space of the bond-domain to prevent the generated bond-domain from overfitting to the source domain. The experimental results show that the proposed algorithm achieves better performance in DukeMTMC-ReID, Market1501 and MSMT17 alternating as the source and the target domain tasks. In the generalization experiments of Market-1501 → DukeMTMC-ReID, mAP and Rank-1 increased by 7.7 % and 3.6 %, respectively, and in the generalization experiments of DukeMTMC-ReID → Market-1501, mAP and Rank-1 are increased by 9.3 % and 3.5 %, respectively, which are significantly better than the newer representative algorithms. [ABSTRACT FROM AUTHOR]

Locally Sensitive Hashing (LSH) algorithms are classical algorithms commonly used on the c-Approximate Nearest Neighbor (c-ANN) search problem. When using Euclidean distance to measure sample similarity and solve the c-ANN problem, the traditional approach is to utilize the Exact Euclidean Locality Sensitive Hashing (E2LSH) algorithm based on the p-stable distribution. However, the uncertainty of the p-stable distribution causes the hash buckets constructed by the E2LSH algorithm to vary in queries. Therefore, this paper proposes the OLLSH algorithm based on the Weighted Majority algorithm in the Online-Learning framework, which selects the hash buckets with more stable query accuracy by weighted voting on the hash buckets generated by the E2LSH algorithm. Then, we conduct simulation experiments on synthetic dataset and four real data sets and conclude that the proposed OLLSH algorithm improves the accuracy compared to the original algorithm with the same memory usage. • The parameters of the E2LSH algorithm are analysed in detail. • The choice of hash buckets for the E2LSH algorithm is achieved with the WM algorithm. • The OLLSH algorithm saves memory by using less hash buckets during the query process. • The efficacy of the OLLSH algorithm was proved on both synthetic and real datasets. [ABSTRACT FROM AUTHOR]

Existing stereo matching algorithms suffer from issues such as susceptibility to distortion, weak noise resistance, and a high rate of mismatches in regions with weak textures and discontinuous disparities. To address these challenges, this paper proposes a stereo matching algorithm based on an improved census transform and minimum spanning tree (MST) cost aggregation. In the cost calculation phase, we employ a Gaussian-weighted transformation window and incorporate gradient and edge information to perform weighted fusion of the results. In the cost aggregation process, we introduce a collaborative adaptive window. Each pixel acquires information from the support window of the guided filter (GF) and other pixels within the MST. Furthermore, we integrate the SLIC superpixel segmentation algorithm into MST construction. These two components work synergistically to assign appropriate adaptive weights to pixels, facilitating coordinated cost volume aggregation. Different optimization methods are applied to address mismatched points of various types in post-disparity processing.Performance evaluation using the Middlebury dataset and KITTI dataset demonstrates that our proposed algorithm not only enhances matching accuracy in regions with discontinuous disparities and weak textures but also exhibits significantly improved robustness to interference. Additionally, the resulting disparity map displays smoother edges. • Cost Calculation Phase: Introducing a Gaussian-weighted transformation window, along with gradient and edge information, enables weighted fusion of results. • Cost Aggregation Process: Collaborative adaptive window introduction allows each pixel to gather information from the support window of the guided filter and neighboring pixels within the Minimum Spanning Tree(MST).Furthermore,the SLIC superpixel segmentation algorithm is integrated into the construction of the MST. • Post-Disparity Processing Optimization: Applying diverse optimization methods addresses mismatches among different types of points. [ABSTRACT FROM AUTHOR]

• A small target detection algorithm based on feature interaction and guided learning. • A feature guided alignment module is designed to obtain more effective features. • Gaussian distribution sample allocation strategy is introduced to obtain better samples. • Feature interaction and decoupling detection enhance the detection task capability. • A new regression loss function is used to optimize the localization ability to a certain extent. At present, for the diverse target sizes, different angles, and complex environment in aerial images, how to detect small objects effectively in aerial images is still a challenge task. In order to further improve the detection accuracy and reduce the missing rate, in this paper, we proposes a small target detection algorithm based on feature interaction and guided learning. Firstly, the feature guided alignment module is designed to deal with the problem of information loss and overlap. Secondly, the misallocation of small object samples is optimized by introducing gaussian sample allocation strategy. Then the interactive parallel detection header is designed to solve the detection task conflict problem. Finally, the new regression loss function is designed to enhance the localization ability of the target. The experimental results on the Tinyperson dataset and Visdrone dataset show that this model can improve the detection accuracy and reduce the missing rate of small targets effectively. [ABSTRACT FROM AUTHOR]

Let G be a finite solvable group, given through a refined consistent polycyclic presentation, and α an automorphism of G , given through its images of the generators of G. In this paper, we discuss algorithms for computing the order of α as well as the cycle length of a given element of G under α. We give correctness proofs and discuss the theoretical complexity of these algorithms. Along the way, we carry out detailed complexity analyses of several classical algorithms on finite polycyclic groups. [ABSTRACT FROM AUTHOR]

Synchronous SGD with data parallelism, the most popular parallelization strategy for CNN training, suffers from the expensive communication cost of averaging gradients among all workers. The iterative parameter updates of SGD cause frequent communications and it becomes the performance bottleneck. In this paper, we propose a lazy parameter update algorithm that adaptively adjusts the parameter update frequency to address the expensive communication cost issue. Our algorithm accumulates the gradients if the difference of the accumulated gradients and the latest gradients is sufficiently small. The less frequent parameter updates reduce the per-iteration communication cost while maintaining the model accuracy. Our experimental results demonstrate that the lazy update method remarkably improves the scalability while maintaining the model accuracy. For ResNet50 training on ImageNet, the proposed algorithm achieves a significantly higher speedup (739.6 on 2048 Cori KNL nodes) as compared to the vanilla synchronous SGD (276.6) while the model accuracy is almost not affected (<0.2% difference). • Adaptive parameter update frequency control for scalable parallel deep learning. • Allowing gradient accumulation considering the direction of the gradients. • Reducing per-iteration communication cost at the input side model layers. • Overlapping gradient communications with backpropagation computations. [ABSTRACT FROM AUTHOR]

• Limited power of randomization in dealing with adaptive adversaries. • Derandomizing algorithms via simulation. • Simulating a dynamic network on top of another dynamic network. This paper investigates the power of randomization in general distributed algorithms in dynamic networks where the network's topology may evolve over time, as determined by some adaptive adversary. In such a context, randomization may help algorithms to better deal with i) "bad" inputs to the algorithm, and ii) evolving topologies generated by "bad" adaptive adversaries. We prove that randomness offers limited power to better deal with "bad" adaptive adversary. We define a simple notion of prophetic adversary for determining the evolving topologies. Such an adversary accurately predicts all randomness in the algorithm beforehand, and hence the randomness will be useless against "bad" prophetic adversaries. Given a randomized algorithm P whose time complexity satisfies some mild conditions, we prove that P can always be converted to a new algorithm Q with comparable time complexity, even when Q runs against prophetic adversaries. This implies that the benefit of P using randomness for dealing with the adaptive adversaries is limited. [ABSTRACT FROM AUTHOR]

In this paper, we consider the sparse phase retrieval problem, recovering an s -sparse signal x ♮ ∈ R n from m phaseless samples y i = | 〈 x ♮ , a i 〉 | for i = 1 , ... , m. Existing sparse phase retrieval algorithms are usually first-order and hence converge at most linearly. Inspired by the hard thresholding pursuit (HTP) algorithm in compressed sensing, we propose an efficient second-order algorithm for sparse phase retrieval. Our proposed algorithm is theoretically guaranteed to give an exact sparse signal recovery in finite (in particular, at most O (log ⁡ m + log ⁡ (‖ x ♮ ‖ 2 / | x min ♮ |)) steps, when { a i } i = 1 m are i.i.d. standard Gaussian random vector with m ∼ O (s log ⁡ (n / s)) and the initialization is in a neighborhood of the underlying sparse signal. Together with a spectral initialization, our algorithm is guaranteed to have an exact recovery from O (s 2 log ⁡ n) samples. Since the computational cost per iteration of our proposed algorithm is the same order as popular first-order algorithms, our algorithm is extremely efficient. Experimental results show that our algorithm can be several times faster than existing sparse phase retrieval algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we consider a class of structured fractional minimization problems where the numerator part of the objective is the sum of a convex function and a Lipschitz differentiable (possibly) nonconvex function, while the denominator part is a convex function. By exploiting the structure of the problem, we propose a first-order algorithm, namely, a proximal-gradient-subgradient algorithm with backtracked extrapolation (PGSA_BE) for solving this type of optimization problem. It is worth pointing out that there are a few differences between our backtracked extrapolation and other popular extrapolations used in convex and nonconvex optimization. One of such differences is as follows: if the new iterate obtained from the extrapolated iteration satisfies a backtracking condition, then this new iterate will be replaced by the one generated from the non-extrapolated iteration. We show that any accumulation point of the sequence generated by PGSA_BE is a critical point of the problem regarded. In addition, by assuming that some auxiliary functions satisfy the Kurdyka-Łojasiewicz property, we are able to establish global convergence of the entire sequence, in the case where the denominator is locally Lipschitz differentiable, or its conjugate satisfies the calmness condition. Finally, we present some preliminary numerical results to illustrate the efficiency of PGSA_BE. [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]

Semi-regular sequences over F 2 are sequences of homogeneous elements of the algebra B (n) = F 2 [ X 1 ,... , X n ] / (X 1 2 ,... , X n 2) , which have as few relations between them as possible. It is believed that most such systems are F 2 -semi-regular and this property has important consequences for understanding the complexity of Gröbner basis algorithms such as F4 and F5 for solving such systems. In fact even in one of the simplest and most important cases, that of quadratic sequences of length n in n variables, the question of the existence of semi-regular sequences for all n remains open. In this paper we present a new framework for the concept of F 2 -semi-regularity which we hope will allow the use of ideas and machinery from homological algebra to be applied to this interesting and important open question. First we introduce an analog of the Koszul complex and show that F 2 -semi-regularity can be characterized by the exactness of this complex. We show how the well known formula for the Hilbert series of a F 2 -semi-regular sequence can be deduced from the Koszul complex. Finally we show that the concept of first fall degree also has a natural description in terms of the Koszul complex. [ABSTRACT FROM AUTHOR]

• Improved distributed approximation for Steiner tree. • Approximation algorithms for Steiner tree in the CONGEST model of distributed computing. • Steiner tree problem in network optimization. In this paper we present two deterministic distributed algorithms for the Steiner tree (ST) problem in the CONGEST model. The first algorithm computes a 2 (1 − 1 / ℓ) -approximate ST using O (S + n log ⁎ ⁡ n) rounds and O (m S + n 3 / 2) messages for a graph of n nodes and m edges, where S is the shortest path diameter of the graph and ℓ is the number of leaf nodes in the optimal ST. It improves the round complexity of the best distributed ST algorithm known so far, which is O ˜ (S + min { S t , n }) [34] , where t is the number of terminal nodes. The second algorithm improves the message complexity of the first one by dropping the additive term of O (n 3 / 2) at the expense of a logarithmic multiplicative factor in the round complexity. We also show that for graphs with S = O (log ⁡ n) , a 2 (1 − 1 / ℓ) -approximate ST can be deterministically computed using O ˜ (n) rounds and O ˜ (m) messages and these complexities almost coincide with the results of some of the singularly-optimal minimum spanning tree (MST) algorithms proposed in [15,22,37]. [ABSTRACT FROM AUTHOR]

• Propose the aligned storage formats ACSR and AELL. • Put forward a parallel SpMV algorithm based on ACSR and AELL formats. • Theoretically analyze the performance of SpMV on ARM processors. • Evaluate the performance of our optimization on Kunpeng 920 processors. Sparse matrix-vector multiplication (SpMV) has always been a hot topic of research for scientific computing and big data processing, but the sparsity and discontinuity of the nonzero elements in a sparse matrix lead to the memory bottleneck of SpMV. In this paper, we propose aligned CSR (ACSR) and aligned ELL (AELL) formats and a parallel SpMV algorithm to utilize NEON SIMD registers on ARM processors. We analyze the impact of SIMD instruction latency, cache access, and cache misses on SpMV with different formats. In the experiments, our SpMV algorithm based on ACSR achieves 1.18x and 1.56x speedup over SpMV based on CSR and SpMV in PETSc, respectively, and AELL achieves 1.21x speedup over ELL. The deviations between the theoretical results and experimental results in the instruction latency and cache access are 10.26% and 10.51% in ACSR and 5.68% and 2.91% in AELL, respectively. [ABSTRACT FROM AUTHOR]

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

In this paper, we introduce the kinetic description of the first-order Cucker-Smale (CS) flocking model on the real line. We reveal the equivalent relation between the measure-valued solution to the first- and second-order kinetic CS equations. The emergent behavior of the first-order kinetic CS equation and the characterization of the asymptotic solution are studied. We also provide the equivalent relation between classical/measure-valued solutions to the first-order kinetic CS equation and a classical solution to the second-order hydrodynamic CS equations, and present the corresponding analysis on the large-time behavior. The numerical experiments support our analysis and provide an efficient algorithm to obtain the asymptotic solution without simulating the model for a long time. [ABSTRACT FROM AUTHOR]

In planar analytic vector fields, a monodromic singularity can be distinguished between a focus or a center by means of the Lyapunov coefficients, which are given in terms of the power series coefficients of the first-return map defined around the singularity. In this paper, we are interested in an analogous problem for monodromic tangential singularities of piecewise analytic vector fields Z = (Z + , Z −). First, we prove that the first-return map, defined in a neighborhood of a monodromic tangential singularity, is analytic, which allows the definition of the Lyapunov coefficients. Then, as a consequence of a general property for pair of involutions, we obtain that the index of the first non-vanishing Lyapunov coefficient is always even. In addition, a general recursive formula together with a Mathematica algorithm for computing the Lyapunov coefficients is obtained. We also provide results regarding limit cycles bifurcating from monodromic tangential singularities. Several examples are analyzed. [ABSTRACT FROM AUTHOR]

In this paper, we prove a supercongruence via the Wilf–Zeilberger method and symbolic summation algorithms in the setting of difference rings. That is, for any prime p > 3 , ∑ n = 0 (p − 1) / 2 3 n + 1 (− 8) n ( 2 n n ) 3 ≡ p (− 1 p) + p 3 4 (2 p) E p − 3 (1 4) (mod p 4) , where (⋅ p) stands for the Legendre symbol, and E n (x) are the Euler polynomials. This confirms a special case of a recent conjecture of Z.-W. Sun (Sun, 2019 , (2.18)). [ABSTRACT FROM AUTHOR]

We show how the classical notions of cohomology with local coefficients, CW-complex, covering space, homeomorphism equivalence, simple homotopy equivalence, tubular neighbourhood, and spinning can be encoded on a computer and used to calculate ambient isotopy invariants of continuous embeddings N ↪ M of one topological manifold into another. More specifically, we describe an algorithm for computing the homology H n (X , A) and cohomology H n (X , A) of a finite connected CW-complex X with local coefficients in a Z π 1 X -module A when A is finitely generated over Z. It can be used, in particular, to compute the integral cohomology H n ( X ˜ H , Z) and induced homomorphism H n (X , Z) → H n ( X ˜ H , Z) for the covering map p : X ˜ H → X associated to a finite index subgroup H < π 1 X , as well as the corresponding homology homomorphism. We illustrate an open-source implementation of the algorithm by using it to show that: (i) the degree 2 homology group H 2 ( X ˜ H , Z) distinguishes between the homotopy types of the complements X ⊂ R 4 of the spun Hopf link and Satoh's tube map of the welded Hopf link (these two complements having isomorphic fundamental groups and integral homology); (ii) the degree 1 homology homomorphism H 1 (p − 1 (B) , Z) → H 1 ( X ˜ H , Z) distinguishes between the homeomorphism types of the complements X ⊂ R 3 of the granny knot and the reef knot, where B ⊂ X is the knot boundary (these two complements again having isomorphic fundamental groups and integral homology). Our open source implementation allows the user to experiment with further examples of knots, knotted surfaces, and other embeddings of spaces. We conclude the paper with an explanation of how the cohomology algorithm also provides an approach to computing the set [ W , X ] ϕ of based homotopy classes of maps f : W → X of finite CW-complexes over a fixed group homomorphism π 1 f = ϕ in the case where dim ⁡ W = n , π 1 X is finite and π i X = 0 for 2 ≤ i ≤ n − 1. [ABSTRACT FROM AUTHOR]

The sparse difference resultant introduced in Li et al. (2015b) is a basic concept in difference elimination theory. In this paper, we show that the sparse difference resultant of a generic Laurent transformally essential system can be computed via the sparse resultant of a simple algebraic system arising from the difference system. Moreover, new order bounds of sparse difference resultant are found. Then we propose an efficient algorithm to compute sparse difference resultant which is the quotient of two determinants whose elements are the coefficients of the polynomials in the algebraic system. The complexity of the algorithm is analyzed and experimental results show the efficiency of the algorithm. [ABSTRACT FROM AUTHOR]

• The placement of data and the scheduling of request are studied in edge caching. • Network unreliability and limited storage and bandwidth resources are considered. • Two algorithms with different computation complexity and cache efficiency are developed. • The experiments are conducted to evaluate the performance of proposed caching strategies. Edge caching is a prevailing media delivery technology where data is hosted at the edge nodes with computing and storage capability in close proximity to users, in order to expand the backhaul network capacity and enhance users' quality of experience (QoE). The existing work in this area often neglects the fact that large-scale distributed cache networks are not particularly reliable and many edge nodes are prone to failure. In this paper we investigate and develop a novel, cooperative caching mechanism for content placement and request routing. We aim to minimize the content access delay and achieve the optimization in polynomial time, taking into account failures in an unreliable network environment with limited edge storage and bandwidth. We introduce two optimization algorithms: 1) a primal-dual algorithm that is based on the Lagrangian dual decomposition and subgradient method, and 2) a greedy-based approximation algorithm with a proven approximation ratio. Numerical results show that the proposed algorithms outperform other comparative approaches in synthetic and real network environments, and the approximation algorithm is particularly suitable for networking scenarios with sparse node connectivity and resources in short supply. [ABSTRACT FROM AUTHOR]

• The Sigmoid algorithm applies the well-known sigmoid function to load balancing. • The algorithm uses all the resources of a system to their fullest requiring no effort. • It adapts to different hardware configurations and application behaviours. • Sigmoid successfully scales to adapt to the systems of the future. A challenge that heterogeneous system programmers face is leveraging the performance of all the devices that integrate the system. This paper presents Sigmoid, a new load balancing algorithm that efficiently co-executes a single OpenCL data-parallel kernel on all the devices of heterogeneous systems. Sigmoid splits the workload proportionally to the capabilities of the devices, drastically reducing response time and energy consumption. It is designed around several features; it is dynamic, adaptive, guided and effortless, as it does not require the user to give any parameter, adapting to the behaviour of each kernel at runtime. To evaluate Sigmoid's performance, it has been implemented in Maat, a system abstraction library. Experimental results with different kernel types show that Sigmoid exhibits excellent performance, reaching a utilization of 90%, together with energy savings up to 20%, always reducing programming effort compared to OpenCL, and facilitating the portability to other heterogeneous machines. [ABSTRACT FROM AUTHOR]

Mobile devices (MDs) and applications are receiving extensive popularity and attracting significant attention. Mobile applications, especially for artificial intelligence (AI) applications, require powerful computation-intensive resources. Hence, running all the AI applications on a single MD introduces high energy consumption and application delay, as it has limited battery capacity and computation resources. Fortunately, the emerging edge-cloud computing (ECC) architecture pushes the computation resource to both the network edge and remote cloud to cope with challenging AI applications. Although the advantage of ECC greatly benefits various mobile applications, data security remains an important open issue in this scenario, which has not been well studied. This paper focuses on the profit maximization (PM) problem for security-aware task offloading in an ECC environment, i.e., considering the tasks from MDs with different service demands, edge nodes should decide them to be processed on the edge node or the remote cloud with a security guarantee. Specifically, we first construct the security model to measure the time overhead for each task under various scenarios. We then formulate the PM problem by jointly considering the security demand and deadline constraints of tasks. Finally, we propose a genetic algorithm-based PM (GA-PM) algorithm, the coding strategy of which considers the task execution location and execution order. Moreover, the crossover and mutation operations are implemented based on the coding strategy. Extensive simulation experiments with various parameters varying demonstrate that our GA-PM can achieve better performance than all the comparison algorithms. • The security model is built to measure the execution time of tasks under different parameters. • A genetic algorithm (GA)-based PM algorithm is proposed to implement task offloading and obtain optimal profit. • A coding strategy is devised by considering the tasks execution location and execution order. • Extensive simulation results demonstrate that GA-PM algorithm achieves the optimal profit. [ABSTRACT FROM AUTHOR]

In this paper we study matching in equational theories that specify counterparts of associativity and commutativity for variadic function symbols. We design a procedure to solve a system of matching equations and prove its termination, soundness, completeness, and minimality. The minimal complete set of matchers for such a system can be infinite, but our algorithm computes its finite representation in the form of solved set. From the practical side, we identify two finitary cases and impose restrictions on the procedure to get an incomplete algorithm, which, based on our experiments, describes the input-output behavior and properties of Mathematica's flat and orderless pattern matching. [ABSTRACT FROM AUTHOR]