This paper studies the minimum weight set cover (MinWSC) problem with a small neighborhood cover (SNC) property proposed by Agarwal et al. in [2]. A parallel algorithm for MinWSC with τ -SNC property is presented, ob...
详细信息
We introduce a distributed memory parallel algorithm for force-directed node embedding that places vertices of a graph into a low-dimensional vector space based on the interplay of attraction among neighboring vertice...
详细信息
ISBN:
(数字)9798350364606
ISBN:
(纸本)9798350364613
We introduce a distributed memory parallel algorithm for force-directed node embedding that places vertices of a graph into a low-dimensional vector space based on the interplay of attraction among neighboring vertices and repulsion among distant vertices. We develop our algorithms using two sparse matrix operations, SDDMM and SpMM. We propose a configurable pull-push-based communication strategy that optimizes memory usage and data transfers based on computing resources and asynchronous MPI communication to overlap communication and computation. Our algorithm scales up to 256 nodes on distributed supercomputers by surpassing the performance of state-of-the-art algorithms.
The increasing scale of power systems necessitates corresponding enhancements in the speed and accuracy of power flow calculations. Leveraging the study of Graphics Processing Unit (GPU) architecture, parallel algorit...
详细信息
ISBN:
(数字)9798331518066
ISBN:
(纸本)9798331518073
The increasing scale of power systems necessitates corresponding enhancements in the speed and accuracy of power flow calculations. Leveraging the study of Graphics Processing Unit (GPU) architecture, parallel algorithms, and power flow calculation methods, we exploit the high parallelism offered by GPU. In this paper, we optimize the Newton method under traditional polar coordinates to develop parallel programs and utilize Compute Unified Device Architecture (CUDA) for data parallel computing. Simulation results demonstrate that as the number of nodes in the test system increases, our proposed program exhibits more pronounced advantages, effectively improving power flow calculation speed and providing a promising approach for further research in this field.
We introduce stronger notions for approximate single-source shortest-path distances, show how to efficiently compute them from weaker standard notions, and demonstrate the algorithmic power of these new notions and tr...
详细信息
parallelized equivalence principle algorithm (EPA) for multiple PEC bodies of revolution (BoR) is proposed. Due to the introduction of the equivalent spheres (ES), the scattering and translation operators of EPA for F...
详细信息
ISBN:
(数字)9798331533922
ISBN:
(纸本)9798331533939
parallelized equivalence principle algorithm (EPA) for multiple PEC bodies of revolution (BoR) is proposed. Due to the introduction of the equivalent spheres (ES), the scattering and translation operators of EPA for Fourier modes can be obtained independently, making the parallel algorithm more efficient. The strategies based on supercomputer architecture for matrix generation and solver are both developed.
For data with complex dimensions, Kernel Principal Component Analysis (KPCA) is a common method of feature extraction, it has a better generalization performance. However, it often face with significant difficulties i...
详细信息
ISBN:
(数字)9798350380958
ISBN:
(纸本)9798350380965
For data with complex dimensions, Kernel Principal Component Analysis (KPCA) is a common method of feature extraction, it has a better generalization performance. However, it often face with significant difficulties in computation on large datasets. Therefore, we developed a parallel KPCA algorithm based on MapReduce (MRKPCA) in this paper, it's a parallel computing method which can run in a cluster. We apply our algorithm to an experiment of datasets of face recognition, the experimental results show that our algorithm can scale well and has better timeliness for some specific problems which require a lot of computation, and it can significantly reduce computation time.
This paper introduces a new class of explanation structures, called robust counterfactual witnesses (RCWs), to provide robust, both counterfactual and factual explanations for graph neural networks. Given a graph neur...
详细信息
ISBN:
(数字)9798350317152
ISBN:
(纸本)9798350317169
This paper introduces a new class of explanation structures, called robust counterfactual witnesses (RCWs), to provide robust, both counterfactual and factual explanations for graph neural networks. Given a graph neural network
$\mathcal{M}$
, a robust counterfactual witness refers to the fraction of a graph
$G$
that are counterfactual and factual explanation of the results of
$\mathcal{M}$
over
$G$
, but also remains so for any “disturbed”
$G$
by flipping up to
$k$
of its node pairs. We establish the hardness results, from tractable results to co-NP-hardness, for verifying and generating robust counterfactual witnesses. We study such structures for GNN-based node classification, and present efficient algorithms to verify and generate RCWs. We also provide a parallel algorithm to verify and generate RCWs for large graphs with scalability guarantees. We experimentally verify our explanation generation process for benchmark datasets, and showcase their applications.
Anomaly detection is a popular research topic in Artificial Intelligence and has been widely applied in network security, financial fraud detection, and industrial equipment failure detection. Isolation forest based m...
详细信息
ISBN:
(数字)9798331506681
ISBN:
(纸本)9798331506698
Anomaly detection is a popular research topic in Artificial Intelligence and has been widely applied in network security, financial fraud detection, and industrial equipment failure detection. Isolation forest based methods are the base algorithms to detect anomalies in these scenarios for their simplicity and efficiency, which has been further exploited with multi-folk trees and learning mechanisms to realize the optimal isolation forest for high detection accuracy. However, the optimal isolation forest is time-consuming with the learning mechanisms, resulting in the task failing of time-constrained applications. Moreover, the original optimal isolation forest fails to construct the optimal tree structure restricted by the time complexity. To address the above challenges, we propose an efficient anomaly detection method called EEIF, which realizes the real e-folk structure of the optimal isolation forest in our practical algorithm design. Specifically, we design a distribution that perfectly matches the e-branch theory to construct the optimal isolation forest. Then, we design an FR clustering scheme to achieve fast training of the isolation forest with learning to hash and provide related proofs of accuracy and efficiency. Besides, a parallel algorithm is integrated into our method to reduce prediction time. Finally, extensive experiments are conducted on a large amount of real-world datasets and the results demonstrate that our method significantly improves efficiency while ensuring effectiveness, compared with the state-of-the-art methods.
In the maximum satisfiability problem (max-sat) we are given a propositional formula in conjunctive normal form and have to find an assignment that satisfies as many clauses as possible. We study the parallel paramete...
详细信息
There has been great interest in the Singular Value Decomposition (SVD) algorithm over the last years because of its wide applicability in multiple fields of science and engineering, both standalone and as part of oth...
详细信息
ISBN:
(数字)9798331534202
ISBN:
(纸本)9798331534219
There has been great interest in the Singular Value Decomposition (SVD) algorithm over the last years because of its wide applicability in multiple fields of science and engineering, both standalone and as part of other computing methods. The advent of the exascale era with massively parallel computers brings incredible possibilities to deal with very large amounts of data, often stored in a matrix. These advances set the focus on developing better scaling parallel algorithms: e.g., an improved SVD to efficiently factorize a matrix. This study assesses the strong scaling of four SVDs of the SLEPc library, plugged into the PETSc framework to extend its capabilities, via a performance analysis on a population of sparse matrices with up to 10 9 degrees of freedom. Among them, there is a randomized SVD with promising performance at scale, a key aspect in solvers for exascale simulations since communication must be minimized for scalability success.
暂无评论