Search

Block matrices with simultaneously diagonalizable blocks arise in diverse application areas, including, e.g., numerical methods for engineering based on partial differential equations as well as network synchronization, cryptography and control theory. In the present paper, we develop a parallel algorithm for the inversion of m × m block matrices with simultaneously-diagonalizable blocks of order n. First, a sequential version of the algorithm is presented and its computational complexity is determined. Then, a parallelization of the algorithm is implemented and analyzed. The complexity of the derived parallel algorithm is expressed as a function of m and n as well as of the number μ of utilized CPU threads. Results of numerical experiments demonstrate the CPU time superiority of the parallel algorithm versus the respective sequential version and a standard inversion method applied to the original block matrix. An efficient parallelizable procedure to compute the determinants of such block matrices is also described. Numerical examples are presented for using the developed serial and parallel inversion algorithms for boundary-value problems involving transmission problems for the Helmholtz partial differential equation in piecewise homogeneous media. [ABSTRACT FROM AUTHOR]

To enhance solution accuracy and training efficiency in neural network approximation to partial differential equations, partitioned neural networks can be used as a solution surrogate instead of a single large and deep neural network defined on the whole problem domain. In such a partitioned neural network approach, suitable interface conditions or subdomain boundary conditions are combined to obtain a convergent approximate solution. However, there has been no rigorous study on the convergence and parallel computing enhancement on the partitioned neural network approach. In this paper, iterative algorithms are proposed to enhance parallel computation performance in the partitioned neural network approximation. Our iterative algorithms are based on classical additive Schwarz domain decomposition methods. For the proposed iterative algorithms, their convergence is analyzed under an error assumption on the local and coarse neural network solutions. Numerical results are also included to show the performance of the proposed iterative algorithms. [ABSTRACT FROM AUTHOR]

In this article, we mainly propose and analyze a parallel stabilized finite element algorithm based upon two-grid discretization for the Navier-Stokes problem. The lowest equal-order finite element pairs are considered for the finite element discretization and a stabilized term based on two local Gauss integrations is introduced to circumvent the discrete inf-sup condition. The main idea is to utilize a partition of unity to assemble weighted local corrections of solutions on sub-domains. A further coarse grid correction is carried out to derive the optimal error estimates both in H 1 norm and L 2 norm. Theoretical results are rigorously established and some numerical experiments are reported to verify the theoretical results. [ABSTRACT FROM AUTHOR]

The single-stack fuel cell system is utilized extensively in several industries. Unfortunately, the main problems are its low efficiency and durability, and unsatisfied reliability, especially in the high-power situation. Due to its significant performance, which includes high output power, durability, and reliability, multi-stack fuel cell systems (MFCS) are becoming more and more attractive. In this study, it is aimed to develope a control algorithm in parallel structure in the Matlab/Simulink software for the efficient use of hydrogen fuel consumption of PEM fuel cells – based boost converter using PI controller with PSO method. Models of both single and parallel connected PEM fuel cells were created in Matlab using mathematical equations in this paper. The analysis made in the study were applied for both models. PEMFCs were connected in parallel and only one DC-DC converter was used for the entire system. According to the load change, the required number of cells are activated due to control algorithm to provide the required power. As a result, the proposed method reduces hydrogen consumption by approximately 5 times under the same load, while optimized parameters reduce output voltage oscillation. • A new control algorithm for parallel connected PEM fuel cell has been successfully implemented. • The suggested method reduces hydrogen consumption by approximately 5 times under the same load. • Using small-capacity fuel cells instead of huge ones minimizes hydrogen consumption. • Optimized parameters decrease the voltage oscillation. [ABSTRACT FROM AUTHOR]

The large deformation of soft rock tunnel is an important problem to be solved urgently with the development of engineering technology. In order to improve the application effect of prestressed anchor cable adaptive active support system, this paper puts forward an optimization method based on adaptive genetic algorithm, reviews the research status of prestressed anchor support in soft rock tunnel, and analyzes and evaluates the existing methods. This paper introduces the construction process of AGA model, establishes the problem description model and genetic optimization algorithm selection model, and constructs the adaptive active support model of prestressed anchor cable. The model adopts an optimization algorithm with a total of 100 iterations. The Simple Genetic Algorithm and Parallel Genetic Algorithm are selected to evaluate the anchoring force, the control effect of surrounding rock displacement, the erosion of supporting structure and the construction time by comparative test. The test results show that AGA has a good effect on the anchoring force, the minimum anchoring force is 457 kN, and the displacement of surrounding rock is controlled within 1.21-1.59mm, which has a good influence on the quality of supporting structure and the construction completion time. Finally, the application of AGA model in parameter optimization of prestressed anchor cable in soft rock tunnel is summarized, and the future research direction is put forward. [ABSTRACT FROM AUTHOR]

This paper focuses on investigating a second-order time parallel decoupled algorithm for the mixed Stokes/Darcy model. The main objective of this algorithm is to deal with the issue of low computational efficiency in solving the coupling problem directly. Our scheme not only reduces the computation scale through the decoupling method, but also realizes the parallelism in the time direction through parareal method. Furthermore, we implement a second-order spectral deferred correction method to improve accuracy. For some small time step size, we prove the stability and convergence results of the time parallel decoupled algorithm. Finally, we provide three numerical tests to demonstrate the reliability and computational efficiency of our algorithm. [ABSTRACT FROM AUTHOR]

In this study, we present a novel interpolation scheme for chimera simulations in CFD that treats flows with discontinuities. This scheme is suitable for interpolation over polyhedral meshes using only scattered data and without the use of stencils. During the interpolation data transfer among overset meshes, both solution variables and their gradients are communicated and then used for the interpolation process. First, the overset topology problem in partitioned polyhedral meshes is addressed, and then a new interpolation algorithm for generally discontinuous fields is introduced. Then, we describe how the gradient approximation of the Finite Volume (FV) method is utilized in order to construct bounded approximations on values on the direction of discontinuities and enhance the accuracy of the low order Nearest Neighbor value (NNV) algorithm. The performance of the proposed algorithm is quantified and validated in various test cases, together with a comparison with NNV. Finally, scalability tests are presented to prove computational efficiency. The method is proved to be highly accurate in propagation cases and performs well in unsteady two-phase problems executed using parallel architectures. [ABSTRACT FROM AUTHOR]

This paper primarily presents a parallel incremental Structure from Motion (ISfM) solution for large-scale images captured by unmanned aerial vehicles (UAVs). The core ideas are a local connection-constrained edge weighting strategy for match graph construction and an anchor-free parallel merging algorithm for the merged model generation. First, an effective algorithm is employed to retrieve spatially overlapped match pairs, utilizing the global descriptor for image representation and the graph indexing for nearest neighbor searching. Second, match pairs are used to create an undirected weighted match graph that is weighted by the local connection strength of the image. This match graph is then used to achieve parallel ISfM through graph clustering. Third, an anchor-free cluster merging algorithm, called AFP-Merging, is then designed by taking advantage of the independent connection between clusters, which increases the merging efficiency and stability. For robust estimation, AFP-Merging is implemented via a bidirectional mean square reprojection error. Finally, extensive evaluation and analysis have been carried out to verify its validation using large-scale UAV datasets captured from classical oblique photogrammetry and recent optimized views photogrammetry. Experiment results show that the proposed solution can generate more compact scene clusters and achieve a speedup ratio greater than 9.0 in cluster merging; compared with recent parallel ISfM, its orientation accuracy is higher in both relative bundle adjustment (BA) without GCPs (Ground Control Points) and absolute BA with GCPs. For the orientation of very large-scale UAV images, it has been successfully applied to a dataset containing ninety thousand images over an area of 50.0 km 2. The proposed method provides a more efficient and reliable parallel SfM solution. The executable tool is made publicly available 1 1 https://github.com/json87/ParallelSfM.. [ABSTRACT FROM AUTHOR]

In this research, we have proposed the parallel GPU-accelerated algorithms to compute the Jacobi moments defined in a rectangular region with substantially improved computational efficiency and highly satisfied accuracy. In our algorithms, the parallel 3-D matrix multiplications are adopted to increase the computational efficiency, while the techniques of coalesced memory access, shared memory and heterogeneous computation are utilized to optimize the computing performance on a GPU platform. Our new GPU-accelerated system can provide any required moment computational accuracy without additional computing time. To verify the performance of our new parallel GPU-accelerated algorithms, we conducted a series of 2D and 3-D image analysis tests via the Jacobi moments with encouraging outcome, while the computing times for all these experimental tasks are in the level of milliseconds. It is expected that our new parallel GPU-accelerated algorithms will expedite the research in 3-D image analysis via the moment methods in the real-time range. [ABSTRACT FROM AUTHOR]

We present a stochastic method for efficiently computing the solution of time-fractional partial differential equations (fPDEs) that model anomalous diffusion problems of the subdiffusive type. After discretizing the fPDE in space, the ensuing system of fractional linear equations is solved resorting to a Monte Carlo evaluation of the corresponding Mittag-Leffler matrix function. This is accomplished through the approximation of the expected value of a suitable multiplicative functional of a stochastic process, which consists of a Markov chain whose sojourn times in every state are Mittag-Leffler distributed. The resulting algorithm is able to calculate the solution at conveniently chosen points in the domain with high efficiency. In addition, we present how to generalize this algorithm in order to compute the complete solution. For several large-scale numerical problems, our method showed remarkable performance in both shared-memory and distributed-memory systems, achieving nearly perfect scalability up to 16 , 384 CPU cores. [ABSTRACT FROM AUTHOR]

The integration of the metaverse with advanced communication networks like 6G underscores the importance of optimizing user experiences. This research introduces a novel approach to addressing traffic prioritization within the metaverse using the Parallel Tempering (PT) algorithm. To ensure adaptive traffic priority management, especially due to the dynamic nature of user interaction, our framework uses temperature in PT chains to model this nature. User activities differ in urgency and importance, each with their respective chains running parallelly with different temperatures. The choice between higher or lower temperatures depends on the application to either exploration (higher temperatures) or exploitation (lower temperatures), which allow adaptation for activity prioritization. As part of the parallel tempering algorithm, chains swap to keep the states with lowest loss with the chains of lower temperature. This exchange of information between chains models the adaptation to user interactions in the metaverse. This research contributes to an adaptive framework for metaverse traffic prioritization, enhancing communication network responsiveness. Our experiments show 7.49% improvement in network latency using the k-medoids algorithm when integrated with parallel tempering in comparison to the traditional k-medoids approach. [ABSTRACT FROM AUTHOR]

In this work, an improved parallel pure meshless algorithm coupling with a high-order time split-step (HSS-IPFPM) is firstly developed to solve the multi-dimensional GPEs, and then the IPFPM is extended to investigate the multi-components CH equations on irregular domain. The proposed meshless method is mainly derived with three points: (a) a fourth-order time-splitting technique is adopted to decompose GPEs, and the high-order derivative is divided into multi-order derivatives; (b) the spatial derivatives are approximated by the Finite Pointset method (FPM) based on the Taylor expansion and weighted least square; (c) the MPI (Message Passing Interface) parallel technique is adopted to reduce the computational cost. Subsequently, the numerical stability and error estimation of the present method are discussed, and the convergent rate and calculated computation of the parallel algorithm are demonstrated by solving four examples. Then the present method is extended to predict inelastic collisions or quantum vortices in GPEs, and phase separation process in multi-component CH. Meanwhile, the merit of easy to implement non-uniformly distributed in the proposed meshless method is illustrated. Finally, the 2D/3D phase separation phenomena in irregular domain are numerically investigated to further demonstrate the capability and applicability of the proposed parallel meshless algorithm. [ABSTRACT FROM AUTHOR]

Clustering methods have become widely popular in the field of data analysis, as they enable the grouping of similar data points. However, the challenge of clustering high-dimensional data remains a significant obstacle due to the "curse of dimensionality." Traditional methods like Principal Component Analysis (PCA) and hierarchy-based feature agglomeration have been used to overcome this challenge by reducing the dimensionality of the dataset. However, there is currently no efficient method for clustering features of a high-dimensional dataset. To address this issue, we present a non-parametric clustering method in this paper, specifically designed for identifying features in a high-dimensional dataset. Our proposed feature clustering algorithm utilizes a partitioning algorithm that creates clusters of features. Through experimental results using publicly available datasets, we demonstrate the effectiveness of our method. Our approach offers a valuable tool for researchers and practitioners to better understand and analyze high-dimensional data. [ABSTRACT FROM AUTHOR]

In this article, a two grid partition of unity finite element method is proposed and investigated for electrically conducting incompressible fluid flows. This algorithm involves solving a much smaller nonlinear problem on a coarse grid, utilizing a partition of unity to decompose reasonably the residual problem into a series of independent subproblems on a fine grid, and carrying out a further coarse correction on the coarse grid. Rigorously theoretical analysis is presented and convergence results indicate that the method could reach the optimal convergence orders with proper configurations between the coarse mesh size H and the fine mesh size h. Finally, some numerical results are reported to verify our theoretical findings. [ABSTRACT FROM AUTHOR]

In this paper, one non-iterative two-grid parallel stabilized finite element method based on overlapping domain decomposition is developed and investigated for the Stokes problem. The lowest-order finite element pairs P 1 − P 1 are utilized to approximate the velocity and pressure, respectively. The difference between a consistent and an under-integrated mass matrices is chosen as the stabilized term to circumvent the so-called inf-sup condition. Algorithm distributes legitimately residuals into local domains with a partition of unity. Error estimates are rigorously established. Theoretical results indicate that patches of diameter H | l n H | (| l n H | − l n | l n H |) or H | l n H | are sufficient to preserve optimal convergence rates with a proper configuration between the coarse mesh size H and the fine mesh size h in 2-D or 3-D case, respectively. Finally, some numerical experiments are reported to support our theoretical results. [ABSTRACT FROM AUTHOR]

Agglomeration-based strategies are important both within adaptive refinement algorithms and to construct scalable multilevel algebraic solvers. In order to automatically perform agglomeration of polygonal grids, we propose the use of Machine Learning (ML) strategies, that can naturally exploit geometrical information about the mesh in order to preserve the grid quality, enhancing performance of numerical methods and reducing the overall computational cost. In particular, we employ the k-means clustering algorithm and Graph Neural Networks (GNNs) to partition the connectivity graph of a computational mesh. Moreover, GNNs have high online inference speed and the advantage to process naturally and simultaneously both the graph structure of mesh and the geometrical information, such as the areas of the elements or their barycentric coordinates. These techniques are compared with METIS, a standard algorithm for graph partitioning, which is meant to process only the graph information of the mesh. We demonstrate that performance in terms of quality metrics is enhanced for ML strategies. Such models also show a good degree of generalization when applied to more complex geometries, such as brain MRI scans, and the capability of preserving the quality of the grid. The effectiveness of these strategies is demonstrated also when applied to MultiGrid (MG) solvers in a Polygonal Discontinuous Galerkin (PolyDG) framework. In the considered experiments, GNNs show overall the best performance in terms of inference speed, accuracy and flexibility of the approach. • New mesh agglomeration strategies driven by Machine Learning techniques. • Geometry-based agglomeration using Graph Neural Networks and K-means clustering. • Reduced computational costs and preservation of grid structure and quality. • Lower iteration counts for agglomeration-based Multigrid solvers. • Fast inference, automatic approach and full data usage with Graph Neural Networks. [ABSTRACT FROM AUTHOR]

In the near future, a much larger scale of low earth orbit (LEO) satellites will be deployed, and satellite selection is an effective way to overcome challenges to processing capability and channel limitation of receivers caused by superabundant satellites in view. However, existing algorithms do not take into account the fact that a large-scale LEO constellation satellite selection subset can be closer to the theoretical optimal configuration than the traditional brute force search and recursive algorithm computational overhead is too large for end devices. In this study, the solution of the minimum optimization problem of the GDOP (Geometric Dilution of Precision) under the condition of limited elevation angle is first analyzed to determine the optimal ratio configuration scheme of top and bottom satellites under the optimal geometric satellite positioning problem. Subsequently, a fast satellite selection algorithm is proposed, which selects a subset of satellites that meet the different numbers of observation satellites and is close to the optimal geometric configuration by geometric method. The comparative simulation shows that, in the 1586 LEO constellation system, the proposed algorithm has an average GDOP of 1.52 when the satellite subset size is 10 and 0.95 when the subset size is 30. Compared with the recursive, the Rotating Partition algorithm and the Quasi-optimal algorithm, the proposed algorithm achieves better accuracy when its size is not close to the total number of observable satellites. [ABSTRACT FROM AUTHOR]

An efficient parallel finite element method is introduced for solving the steady-state Smagorinsky model in which a fully overlapping domain decomposition is considered for parallelization. The crucial idea of the method is to utilize a locally refined multiscale mesh that is fine around its own subdomain and coarse elsewhere to calculate a local finite element solution. On the basis of an existing Smagorinsky solver, the introduced method is easily implemented and avoids massive recoding. Using the duality argument, errors of the standard finite element approximations for the velocity in L 2 norm and pressure in H − 1 norm are derived. Error bounds of the solutions from the introduced method are estimated. Moreover, four parallel iterative algorithms are presented, and some results of numerical tests are given to verify the theory predicted and demonstrate the effectiveness of the algorithms. It is numerically shown that the parallel algorithms decrease substantially the CPU time, keeping the accuracy of the solutions comparable to the serial algorithm. [ABSTRACT FROM AUTHOR]

We study variational inequalities over the solution sets of split variational inclusion problems with multiple output sets. In order to find a solution to such problems, we introduce a new parallel iterative algorithm by combining the inertial forward–backward splitting method with the steepest descent method. Our algorithm does not depend on the norm of the transfer mappings. Some of its applications to solving split common null point, split minimum point, and split common fixed point problems are also given. [ABSTRACT FROM AUTHOR]

Nowadays, the growing interest in industry for enhancing the sustainability of manufacturing processes is becoming a major trend. Energy consumption can be lowered by controlling machine states with energy-efficient control policies that switch off/on the device. Recent studies have shown that Reinforcement Learning algorithms can effectively control manufacturing systems without the requirement of prior knowledge about system parameters. This is a significant factor since full information on system dynamics is difficult to obtain in real-world applications. This work proposes a new Reinforcement Learning-based algorithm to apply energy-efficient control strategies to a single workstation consisting of identical parallel machines. The model goal is to achieve the optimum trade-off between system productivity and energy demand without relying on full knowledge of the system dynamics. Numerical experiments confirm effectiveness, applicability, and generality of the proposed approach, even when applied to a real-world industrial system from the automotive sector. [ABSTRACT FROM AUTHOR]

Wind speed is the dominant meteorological factor affecting wind turbine power generation. Existing wind speed fluctuation division algorithms only focus on the wind speed changing process, but strong uncertainty exists in the wind speed–power conversion, which has been demonstrated as a multi-power transfer relationship under wind speed fluctuation. Therefore, a wind speed power transfer fluctuation partitioning (PTFP) algorithm is proposed, which fully considers the wind speed variation and power transfer characteristics to refine the modeling of wind power forecasting. The power transfer characteristics are investigated according to the wind speed–power conversion error of a wind farm. The measured wind speeds from three sources and fuzziness under different fluctuation trends are discussed based on the scatter distribution and probabilistic wind speed power curve. The model errors under different changing trends are quantitatively analyzed. Subsequently, the operation data of two wind farms in China are divided using the PTFP algorithm. The modeling error is reduced compared to that without considering the power transfer characteristics and the rationality of the proposed algorithm is demonstrated. The PTFP algorithm is also applied to wind power forecasting to verify its applicability. The results demonstrate that the proposed model can improve prediction accuracy on all time scales. [ABSTRACT FROM AUTHOR]

Parallel and distributed stochastic algorithms have drawn significant attention in the realm of big data and machine learning. While the synchronous versions of these algorithms are well understood in terms of their convergence, the convergence analyses of their asynchronous counterparts are not widely studied. In this paper, we propose and analyze a distributed, asynchronous parallel algorithm to solve an arbitrary, consistent linear system by reformulating the system into a stochastic optimization problem as Richtárik and Takác̃ in [1]. We compare the convergence rates of our asynchronous algorithm with the synchronous parallel algorithm proposed by Richtárik and Takáč in [1] under different choices of the hyperparameters—the stepsize, the damping factor, the number of processors, and the delay factor. We show that our asynchronous parallel algorithm enjoys a global linear convergence rate, similar to the synchronous parallel algorithm in [1] under the same setup. We also show that our asynchronous algorithm improves upon the synchronous algorithm in [1] with a better convergence rate when the number of processors is larger than four. Furthermore, our asynchronous parallel algorithm performs asymptotically better than its synchronous counterpart for certain linear systems. Finally, we compute the minimum number of processors required for those systems for which our asynchronous algorithm is better and find that this number can be as low as two for some ill-conditioned problems. [ABSTRACT FROM AUTHOR]

• The TRV can improve performance by reducing the number of iterations. • Accurate periods can be quickly derived using the TRV. • The near-accurate poles can be derived when using the TRV with enough lightcurves. • OpenMP and CUDA C can largely improve the computational efficiency of the TRV. Asteroids, especially near-Earth asteroids, have become a popular focus of research in the field of deep space exploration because they retain historical relics of the early formation and evolution of the Solar System. Rotational periods play an important role in elucidating the characteristics of asteroids, such as the rubble-pile internal structure and the spin barrier. Generally, commonly used periodogram methods, such as Fourier-type methods, can produce only a rough estimate of the rotational period, and it is difficult to obtain other essential parameters, such as the pole, shape, and scattering parameters. To alleviate this problem, this article presents a three-step reduced voting (TRV) algorithm based on the Cellinoid model to accurately and efficiently invert asteroidal periods from lightcurves. The proposed TRV algorithm can realize this inversion process to derive the high-precision period, as well as a roughly estimated pole orientation and overall shape of an asteroid. Numerical experiments confirm that the TRV algorithm can obtain accurate periods and near-accurate poles from synthetic lightcurves. Besides, this algorithm is applied to invert the rotational periods of the 61 real asteroids, and the derived periods are consistent with those reported in other publications. It is also demonstrated that more observations collected in various viewing geometries can improve the accuracy in searching the pole orientation of an asteroid. For further improving the efficiency of TRV, parallel versions of this algorithm implemented with OpenMP and CUDA C schemes are provided with environments of Hygon C86 7185 CPUs and a Tesla V100-SXM3 GPU, respectively. The maximum speedup ratio of the OpenMP scheme is 79.567x, while that of the CUDA C scheme is 110.906x. The results show that the proposed parallel acceleration schemes can greatly improve the inversion efficiency of the TRV algorithm, and can be widely used in searching the parameters of a large number of asteroids. [ABSTRACT FROM AUTHOR]

Highly complex and dense models of 3D objects have recently become indispensable in digital industries. Mesh decimation then plays a crucial role in the production pipeline to efficiently get visually convincing yet compact expressions of complex meshes. However, the current pipeline typically does not allow artists control the decimation process, just a simplification rate. Thus a preferred approach in production settings splits the process into a first pass of saliency detection highlighting areas of greater detail, and allowing artists to iterate until satisfied before simplifying the model. We propose a novel, efficient multi-scale method to compute mesh saliency at coarse and finer scales, based on fast mesh entropy of local surface measurements. Unlike previous approaches, we ensure a robust and straightforward calculation of mesh saliency even for densely tessellated models with millions of polygons. Moreover, we introduce a new adaptive subsampling and interpolation algorithm for saliency estimation. Our implementation achieves speedups of up to three orders of magnitude over prior approaches. Experimental results showcase its resilience to problem scenarios that efficiently scales up to process multi-million vertex meshes. Our evaluation with artists in the entertainment industry also demonstrates its applicability to real use-case scenarios. [Display omitted] • A novel multi-scale mesh saliency formulation, configurable by one hyperparameter. • An adaptive subsampling scheme which allows for speed-ups of up to three orders of magnitude at close to no introduced error. • An evaluation of our method in a production pipeline in the entertainment industry. • An interactive GUI to control the method that interfaces with common industry tools. [ABSTRACT FROM AUTHOR]

This work studies a parallel grad-div stabilized finite element algorithm for the damped Stokes equations. In this algorithm, in the light of a fully overlapping domain decomposition technique, we solve a global grad-div stabilized problem to compute a local solution in an intersecting subdomain on a global composite mesh, which is fine in the subdomain and rough elsewhere, making the proposed algorithm easy to implement based on an available sequential solver. We derive error bounds of the approximate solutions from our presented algorithm by the theoretical tool of local a priori estimate for the grad-div stabilized finite element solution. Numerical results verify the validity of the theoretical analysis and demonstrate the benefits of the proposed algorithm. On the one hand, compared with the counterpart one excluding grad-div stabilization, this algorithm can reduce significantly the effect of pressure on the approximate velocities, and hence, yields much better approximate velocities in the case of small viscosities. On the other hand, it takes much less computational time in getting approximate solutions with a comparable accuracy than the standard grad-div stabilization method. [ABSTRACT FROM AUTHOR]

For efficient design of parallel algorithms on multiprocessor architectures with memory banks, simultaneous access to a specified subgraph of a graph data structure by multiple processors requires that the data items belonging to the subgraph reside in distinct memory banks. Such "conflict-free" access to parallel memory systems and other applied problems motivate the study of rainbow coloring of a graph, in which there is a fixed template T (or a family of templates), and one seeks to color the vertices of an input graph G with as few colors as possible, so that each copy of T in G is rainbow colored, i.e., has no two vertices the same color. In the above example, the data structure is modeled as the host graph G , and the specified subgraph as the template T. We call such coloring a template-driven rainbow coloring (or TR -coloring). For large data sets, it is also important to ensure that no memory bank (color) is overloaded, i.e., the coloring is as balanced as possible. Additionally, for fast access to data, it is desirable to quickly determine the address of a memory bank storing a data item. For arbitrary topology of G and T , finding an optimal and balanced TR -coloring is a challenging problem. This paper focuses on rainbow coloring of proper interval graphs (as hosts) for cycle templates. In particular, we present an O (k ⋅ | V | + | E |) time algorithm to find a TR -coloring of a proper interval graph G with respect to k -length cycle template, C k. Our algorithm produces a coloring that is (i) optimal , i.e., it uses minimum possible number of colors in any TR -coloring; (ii) balanced , i.e, the vertices are evenly distributed among the different color classes; and (iii) explicit , i.e., the color assigned to a vertex can be computed by a closed form formula in constant time. [ABSTRACT FROM AUTHOR]

In this paper, we introduce and study a highly scalable domain decomposition based solver for the fully implicit solution of subsurface flows in porous media with fractional derivative. In the proposed approach, a fully implicit scheme is proposed to relax the time step size by the stability condition, and the Newton–Krylov method is then applied to guarantee the nonlinear consistency of the resultant algebraic system. Moreover, to accelerate the convergence of the Newton iterations and be favorable for the scalability of the linear solver, the emphasis is placed on introducing the overlapping restricted additive Schwarz (RAS) preconditioners. Numerical experiments are presented to demonstrate the robustness and parallel scalability of the proposed fully implicit algorithm for some subsurface flow problems on a supercomputer. [ABSTRACT FROM AUTHOR]

The Graph Partitioning Problem (GPP) is a classical combinatorial optimization problem that has been extensively researched. In recent years, many methods for solving the GPP have been proposed, which can be divided into direct partitioning approaches and iterative improvement approaches. Direct partitioning approaches directly give a complete partition of the input graph. Iterative improvement approaches require further adjustment of feasible solutions based on the result of direct partitioning approaches in order to obtain a better performance. In this paper, we summarize the recent trends in algorithms and applications for GPP. In addition, we propose a graph partitioning algorithm based on semi-supervised learning in combination with graph filtering methods. [ABSTRACT FROM AUTHOR]

The cost of some primitive operations such as multiplication and division significantly affects the running time of some applications in science and engineering especially when the size of data is big. In this study, we propose a formula to minimize the cost of the multiplication operation on integer numbers when the size of each integer and the number of integers to be multiplied are large. Based on a window strategy, we derived, theoretically, the best size of window for minimizing the cost of multiplying a sequence of big integers. To the best of our knowledge, no previous studies have proposed this formula. Then we designed three efficient algorithms, one sequential and two parallel. Experimental studies were conducted using three parameters: (1) the size of integer, (2) the size of a sequence, and (3) the number of threads. The results of a comparison with the best known previous algorithms showed that (1) the designed sequential algorithm is faster than the previous algorithms with an improvement greater than 64 % , (2) the designed parallel algorithms are faster than the best known parallel algorithm with an improvement greater than 50 % on the average, and (3) the designed parallel algorithms have super linear speed up. [ABSTRACT FROM AUTHOR]

• A time-varying external archive differential evolution can obtain multiple roots for system of nonlinear equations. • A judgment criterion dividing individuals into the ordinary, local and global optimal subpopulations is proposed. • A new difference mutation vector is used to ensure the diversity of the population. • The generality, computation efficiency, and applicability of the proposed method are verified. In this work, a time-varying external archive differential evolution algorithm is proposed, which can obtain the multiple roots for system of nonlinear equations for the forward displacement of parallel mechanisms. In time-varying external archive differential evolution three improvements are presented. At first, a time-varying subpopulation strategy is proposed to consider both global and local searching capabilities. Then, an individual judgment criterion is proposed, which employs the weighted basis vector mutation strategy for ordinary individuals and a hybrid mutation operator for locally optimal individuals. Finally, the external archive strategy of neighborhood-based crowding differential evolution is improved to enhance the domain searching ability of the algorithm. To evaluate the performance of time-varying external archive differential evolution, twenty benchmark functions are selected as the test suite. Moreover, the solutions for forward displacements of four strongly coupled parallel mechanisms with different degrees of freedom are derived to test the generality of this method. From the acquired experimental results, it is demonstrated that fairly-competitive results can be provided compared to other methods, in both benchmark functions and forward displacement solutions of parallel mechanisms. [ABSTRACT FROM AUTHOR]

This work presents a hybrid sliding mode controller approach for level control in the nuclear power plant steam generators. In a nuclear power plant, the steam generator is one of the essential pieces of equipment. Therefore, this paper aims at a robust hybrid scheme that merges internal model control concepts, sliding mode control methodology, and gain scheduling using Takagi–Sugeno multimodel fuzzy systems. Since the process presents integrating and inverse response with dead time and a highly dependent response associated with the operating power variability, this work considers process identification like an optimization problem. Hence, parallel processing algorithms such as particle swarm optimization are used. The performance achieved with the new proposal is suitable for set-point tracking and disturbance rejection. [ABSTRACT FROM AUTHOR]

The problems of recognizing series–parallel graphs, outerplanar graphs, and generalized series–parallel graphs have been studied separately in the past. Efficient algorithms have been presented. However, none of the algorithms are certifying. A certifying algorithm generates, in addition to its answer, a certificate that can be used by a checker (a separate algorithm) to verify the correctness of the answer. The certificate is positive if the answer is 'yes', and is negative if the answer is 'no'. In this paper, an O (| E | + | V |) -time certifying algorithm that simultaneously determines if a graph G = (V , E) is series–parallel, outerplanar, or generalized series–parallel is presented. The positive certificates are a construction sequence for constructing G if G is series–parallel, a generalized construction sequence for constructing G if G is generalized series–parallel but not series–parallel, and the edge set of the exterior boundary of an outerplanar embedding of G if G is outerplanar. The negative certificates are forbidden subgraphs or forbidden structures of G. All these certificates are generated by making only one pass over G after a preprocessing step decomposing G into its biconnected components. [ABSTRACT FROM AUTHOR]

The line graphs of some well-known graphs, such as the generalized hypercube and the crossed cube, have been adopted for the logic graphs of data center networks (DCNs). Conditional bijective connection networks (conditional BC networks) are a class of networks which have been proved to include hypercubes, crossed cubes, locally twisted cubes and Möbius cubes, etc. Hence, the researches on the line graphs of conditional BC networks can be applied to DCNs. Edge independent spanning trees (EISTs) on a graph have received extensive attention because of their applications in reliable communication, fault-tolerant broadcasting and secure message distribution. Since the line graph of an n -dimensional conditional BC network, denoted as L (X C n) , is (2 n − 2) -regular, whether there exist 2 n − 2 EISTs on L (X C n) is an open question. In this paper, we first propose a parallel algorithm to construct 2 n − 2 EISTs rooted at an arbitrary node on L (X C n) , where n ≥ 2. Then, we prove the correctness of our algorithm. Finally, we give a simulation result of our algorithm. [ABSTRACT FROM AUTHOR]

We investigate two parallel dedicated machine scheduling with conflict constraints. The problem of minimizing the makespan has been shown to be NP-hard in the strong sense under the assumption that the processing sequence of jobs on one machine is given and fixed a priori. The problem without any fixed sequence was previously recognized as weakly NP-hard. In this paper, we first present a 9 5 -approximation algorithm for the problem with a fixed sequence. Then we show that the tight approximation ratios of the algorithm are 7 4 and 5 3 for two subproblems which remain strongly NP-hard. We also send an improved algorithm with approximation ratio 3 − 2 ≈ 1.586 for one subproblem. Finally, we prove that the problem without any fixed sequence is actually strongly NP-hard, and design a 5 3 -approximation algorithm. • Consider the problem of scheduling with conflict constraints on two parallel dedicated machines. • Present a 9 5 -approximation algorithm for the strongly NP-hard case where jobs on one machine have a fixed processing sequence, and give improvements to its hard subproblems. • Prove that the problem without any fixed sequence is strongly NP-hard too and propose a 5 3 -approximation algorithm. [ABSTRACT FROM AUTHOR]

A multi-parameter sensitivity analysis method was proposed based on Latin hypercube sampling and the rank correlation method. The general genetic algorithm was improved by incorporating a niche parallel algorithm, suspicious peak point judgment, and a local search strategy, and both the improved genetic algorithm and multi-parameter sensitivity analysis method were implemented through C++ programming. The hydrogen pressure-composition isotherm (PCT curve) was found to play an important role in the study of hydrogen storage properties of metallic materials, and its reaction enthalpy change term was widely replaced by a power series form of smoothing. Based on the improved multi-parameter sensitivity analysis method, the effects of the range of parameter values and the number of samples on sensitivity were investigated, where the sensitivity ranking of the 10 parameters in the classical model was obtained. In addition, the equilibrium hydrogen pressure expression models of the highest order i of the power series from 3 to 9 were developed. The influence of the highest order on the optimization of multi-parameter identification was compared using an improved genetic algorithm, and we concluded that the eighth order polynomial model had the optimal convergence and fitting effect. Based on the inspiration of the function trend shape, two innovative forms of the PCT model power series were proposed in this work. Combined with typical examples, three high-order models were fully evolved, and a better power series form was obtained compared to the traditional model. • Two improved approaches were used to smooth-fit the hydrogen pressure-composition isotherm (PCT curve). • Based on the inspiration of function trend shape, two innovative forms of the PCT model power series were proposed. • The influencing factors of parameter sensitivity of PCT curve were determined and the applicable conditions were discussed. • The PCT curve optimized by intelligent algorithm was in good agreement with the experimental value. • An evolution process of one new power series form was more excellent than the classic one. [ABSTRACT FROM AUTHOR]

UDDSketch is a recent algorithm for accurate tracking of quantiles in data streams, derived from the DDSketch algorithm. UDDSketch provides accuracy guarantees covering the full range of quantiles independently of the input distribution and greatly improves the accuracy with regard to DDSketch. In this paper we show how to compress and fuse two or more data streams (or datasets) by leveraging the mergeability of the UDDSketch data summaries. In general, two summaries on two data streams are said to be mergeable if there exists an algorithm that allows combining the two summaries into a single one related to the union of the two datasets, simultaneously preserving the error and size guarantees. The property of mergeability of a sketch enables the parallel and distributed processing of big volume data streams that can be compressed and fused by means of such mergeable data structures. Among the applications strictly related to accurate tracking of quantiles, requiring parallel and/or distributed processing we recall here estimating the latency of a web site, database query optimizers and the need of succinctly summarizing the distribution of values occurring over a sensor network. We prove that UDDSketch is fully mergeable and introduce PUDDSketch , a parallel version of UDDSketch suitable for message-passing based architectures. We formally prove its correctness and compare it to a parallel version of DDSketch , showing through extensive experimental results that our parallel algorithm almost always outperforms the parallel DDSketch algorithm with regard to the overall accuracy in determining the quantiles. Moreover, we also design and implement parallel versions of both the state of the art KLL and REQ sequential algorithms in order to compare and contrast PUDDSketch versus the corresponding parallel algorithms. Our experiments clearly show that PUDDSketch is faster or on par with regard to parallel running time, whilst providing simultaneously greater accuracy. • We prove that the UDDSketch algorithm for tracking quantiles is fully mergeable. • We design PUDDSketch , a parallel version for message-passing architectures. • PUDDSketch can compress and fuse data streams or datasets. • Regarding accuracy, PUDDSketch outperforms competing algorithms. • Regarding parallel running time, PUDDSketch is faster or on par. [ABSTRACT FROM AUTHOR]

We present a high order finite difference solver, ParaTC, for the direct numerical simulations of turbidity currents with canonical turbulent channel configuration (periodic boundary conditions in the horizontal directions and non-periodic in vertical direction). Uniform meshes are adopted in streamwise and spanwise directions, while stretched grids can be used in wall-normal direction. In order to improve the parallel efficiency, we propose a new 2D pencil-like parallel configuration with totally 6 different pencil arrangements. A parallel Thomas algorithm is also included to further reduce the communication overhead when solving tridiagonal equations. In addition, we perform an optimal search method in the initializing stage to find the fastest Poisson solver scheme among four alternatives for a specific mesh configuration. The runtime ratio between traditional pencil-like Poisson solver and present solver is about 1.5. An approximate linear strong scaling performance is achieved, and the weak scaling performance is also improved. Three benchmark simulations are preformed, and the statistics are compared with those extracted from the simulations by the spectral method, and good agreements are achieved. The source code is freely available at https://github.com/GongZheng-Justin/ParaTC. [ABSTRACT FROM AUTHOR]

• Systematically consider time-varying traffic conditions and system-wide impact in urban city logistic problem. • Incorporate parsimonious road link travel time functions with First-In-First-Out property. • Develop three unified optimization models for characterizing problem-specific features in real-life rich arc routing applications. • Exact solution algorithms using Lagrangian relaxation and branch-and-price methods. City logistics, as an essential component of the city operation system, aims at managing the complex flow of goods and services from providers to customers efficiently. Delays associated with peak-period traffic congestion exists in both large and small metropolitan areas. As many of the service tasks in city logistics are needed to be performed during peak hours, operators of urban management movement should consider reducing the total trip time and delay when designing service plans. Equally important, the congestion impact of service vehicles to other road users should also be considered. In this paper, we focus on formulating and solving rich arc routing problems (RARPs) in city logistics with a congested urban environment. We highlight the needs of embedding a structurally parsimonious time-dependent travel time model in RARP for producing high-quality and practically useful solutions. A fluid queue model based analytical approach is presented for link travel time calibration in the form of polynomial arrival rate functions. Accordingly, system-wide (societal) impact of vehicles routing is analytically derived and incorporated into the RARP models which enables traffic managers to systematically consider operation costs and societal impacts when designing routing policies in real-life city logistics applications. Additionally, we develop two new representation schemes for time-dependent travel time modeling in RARPs, including a discretized time-expanded representation scheme and a nonlinear polynomial representation scheme. Three modeling approaches for RARPs are proposed, with different perspectives of capturing time-dependent travel time and formulating problem-specific constraints. With a real-life sprinkler truck routing problem as the representative example of RARP, we develop two efficient exact solution algorithms, including a Lagrangian relaxation-based method and a branch-and-price based method. The latter one is embedded with an enhanced parallel branch-and-bound algorithm. Extensive numerical experiments are conducted based on real-world networks and traffic flow data to demonstrate the effectiveness of the proposed methods. [ABSTRACT FROM AUTHOR]

The aim of this paper is to present a parallel distributed version of Viterbi algorithm that combines the advantages of Spark, the big data framework, and hidden Markov models to solve the decoding problem for large scale multidimensional data. The scope of the paper includes a review of hidden Markov models, a study of decoding problem, a presentation of related work, and a discussion of previously proposed implementations. The main part of the paper consists of a description of development and implementation of a parallel distributed Viterbi algorithm in a cloud computing environment, followed by a description of evaluation experiments of the presented algorithm. The results showed that the proposed algorithm is faster, with high scalability and no deterioration in forecast accuracy is observed. [ABSTRACT FROM AUTHOR]

Intercity Demand Responsive Transit (IDRT) systems, providing on-demand "door-to-door" services for intercity travelers, have been recently implemented in a few cities and gained popularity. To devise a theoretical tool for designing efficient IDRT systems, this study proposes a continuous approximation (CA) model to describe the operation metrics of the IDRT. In a two-city system, an optimization model is proposed to study the zoning strategies in the main city, the service area in the satellite city, and headways. The objective is to minimize the average system cost, including the costs of both the operators and the passengers. A two-stage partition algorithm is proposed to generate a near-optimal solution by combining the greedy algorithm and sensitivity-based coordination optimization method. Subsequently, we develop a direct solution algorithm to establish a lower bound for the optimal solution, facilitating a comparison with the near-optimal solution. Throughout all sensitivity analyses, the gaps between the near-optimal solution and the lower-bound solution remain below 3 %. The comparison results demonstrate that the computation time and solution quality of the two-stage partition algorithm are considered acceptable. Simulation is performed to test the validity of the CA model, and the errors in the average system costs are less than 1.16 %. Sensitivity analyses are carried out to evaluate the impacts of several key parameters (e.g., demand densities and line-haul distances) on the optimization results. By comparison with Intercity Fixed Route Transit (IFRT), it can be seen that the choice of IDRT depends on passengers' preference for door-to-door transportation. This study may serve as a valuable reference for the practical implementation of IDRT. [ABSTRACT FROM AUTHOR]

Parallel Surrogate-Based Optimization (PSBO) is an efficient approach to deal with black-box time-consuming objective functions. According to the available computational budget to solve a given problem, three classes of algorithms are investigated and opposed in this paper: Bayesian Optimization Algorithms (BOAs), Surrogate-Assisted Evolutionary Algorithms (SAEAs) and Surrogate-free Evolutionary Algorithms (EAs). A large set of benchmark functions and engineering applications are considered with various computational budgets. In this paper, we come up with guidelines for the choice between the three categories. According to the computational expensiveness of the objective functions and the number of processing cores, we identify a threshold from which SAEAs should be preferred to BOAs. Based on this threshold, we derive a new hybrid Bayesian/Evolutionary algorithm that allows one to tackle a wide range of problems without prior knowledge of their characteristics. [ABSTRACT FROM AUTHOR]

• A noval polygon structural primitive partitioning algorithm. • An innovative multi-robot collaboration path planning method based on structural primitive partitioning. • Developed an integrated process planning software for DED-Arc. • A manufacturing case shows that the method can be used in industrial production. Directed Energy Deposition (DED) technology is increasingly favored for swiftly fabricating large structural components due to its high printing efficiency. Despite its advantages, challenges persist in achieving satisfactory surface finish and forming precision, hindering its widespread adoption across industries. To address these issues, this paper presents a novel multi-robot collaborative path planning method based on structural primitive partitioning. This method simplifies path planning complexities and seamlessly integrates into process planning software, thereby enhancing overall functionality. This method decomposes complex polygons into tiny primitives (TP), organizing them into TP sets based on bridge and adjacency relations. These sets are then structured into first-level structural TP (F-TP) and second-level structural TP (S-TP), followed by the establishment of monotonic structural TP (M-TP). A minimum rectangular box recalculates the filling path for each M-TP, while the external contour path and internal zigzag path form a complete printing path. Additionally, an optimal printing sequence planning algorithm for multi-robot using a KD-tree-based search algorithm is presented, ensuring the shortest non-productive path and collision avoidance during printing. Experimental verification with four structures of varying geometric features demonstrates a partitioning accuracy of 99.5 % and absence of surface defects in the printed parts. The proposed method presents a viable and effective solution for enhancing the quality of parts produced via DED. [ABSTRACT FROM AUTHOR]

In global routing, congestion and running time are the key factors that affect the quality of the solution. With the rapid growth of integrated chip scale, striking a balance between running time and congestion has become a bottleneck in improving design quality. In this paper, we propose a highly efficient and effective global router to address this challenge. We first propose an efficient R-tree-based compatible routing region partitioning algorithm for collecting routable regions, which offers robust support for ideal parallel routing scheduling. Then, taking into account the effect of the barrel effect on congestion evaluation and the detrimental impact of loops, a congestion-driven initial parallel routing scheme is proposed to enhance routability in the triaxial pattern routing structure. After that, we develop an accurate congestion estimation model and an optimized path-searching scheme, which are instrumental in effectively managing smaller congestion gradient variations and guiding efficient congestion reduction. We evaluate the performance of our algorithm on the ISPD 2018 and ISPD 2019 contest benchmark suites and compare it with the state-of-the-art work. Experimental results show that our proposed algorithm significantly reduces 71% overflows, improving 65% running time, and the total wirelength is even smaller. [ABSTRACT FROM AUTHOR]

Graph entity dependencies (GEDs) are novel graph constraints, unifying keys and functional dependencies, for property graphs. They have been found useful in many real-world data quality and data management tasks, including fact checking on social media networks and entity resolution. In this paper, we study the discovery problem of GEDs—finding a minimal cover of valid GEDs in a given graph data. We formalise the problem, and propose an effective and efficient approach to overcome major bottlenecks in GED discovery. In particular, we leverage existing graph partitioning algorithms to enable fast GED-scope discovery, and employ effective pruning strategies over the prohibitively large space of candidate dependencies. Furthermore, we define an interestingness measure for GEDs based on the minimum description length principle, to score and rank the mined cover set of GEDs. Finally, we demonstrate the scalability and effectiveness of our GED discovery approach through extensive experiments on real-world benchmark graph data sets; and present the usefulness of the discovered rules in different downstream data quality management applications. • A study of the discovery problem of Graph Entity Dependencies (GEDs). • A new and efficient approach for the discovery of GEDs in property graphs. • A minimum description length inspired definition of interestingness of GEDs to rank discovered rules. • A thorough empirical evaluation of the proposed technique, with examples of useful rules (mined) that are relevant in data quality/management applications. [ABSTRACT FROM AUTHOR]

We propose a parallel multi delay (PMD) carrier-assisted differential detection (CADD) receiver for the first time, including PMD asymmetric-CADD (PMD A-CADD) and PMD symmetric-CADD (PMD S-CADD). The transfer function of the PMD CADD receiver is optimized by expanding the number of optical delays to a general selection, thereby suppressing the signal-signal beat interference (SSBI). As a result, the required carrier-to-signal power ratio (CSPR) is reduced, and the optical signal-to-noise ratio (OSNR) sensitivity is drastically improved. Two schemes for further mitigation of residual SSBI are introduced, namely SSBI iterative cancellation algorithm and the increased guard band mitigation method. For SSBI iterative cancellation algorithm, by optimizing the number of optical delays, the optimal CSPR for the P6D A-CADD and the P5D S-CADD can be reduced to −1 dB, the required number of iterations is only 3, and compared with the parallel dual delay-based asymmetric-CADD (PDD A-CADD) receiver, the OSNR sensitivity is improved by about 4.5 dB. For the increased guard band mitigation method, 2.34 GHz and 3.16 GHz guard band are required for the P6D A-CADD and the P5D S-CADD to meet the 7% FEC threshold at 0 dB CSPR. • A parallel multi delay CADD receiver is proposed for data center interconnect applications. • The proposed receiver suppresses SSBI by modifying the transfer function, thereby reducing the optimal CSPR to less than 0 dB. • Two SSBI iteration cancellation algorithms are used to improve the system performance, and the SSBI simplified iteration cancellation algorithm had lower complexity and better performance. [ABSTRACT FROM AUTHOR]