检索结果-内蒙古大学图书馆

12th Innovations in Theoretical Computer Science Conference, ITCS 2021

作者： Anari, Nima Hu, Nathan Saberi, Amin Schild, Aaron Stanford University CA United States University of Washington SeattleWA United States

ISBN: (纸本)9783959771771

We study the problem of sampling a uniformly random directed rooted spanning tree, also known as an arborescence, from a possibly weighted directed graph. Classically, this problem has long been known to be polynomial-time solvable;the exact number of arborescences can be computed by a determinant [33], and sampling can be reduced to counting [18, 16]. However, the classic reduction from sampling to counting seems to be inherently sequential. This raises the question of designing efficient parallel algorithms for sampling. We show that sampling arborescences can be done in RNC. For several well-studied combinatorial structures, counting can be reduced to the computation of a determinant, which is known to be in NC [9]. These include arborescences, planar graph perfect matchings, Eulerian tours in digraphs, and determinantal point processes. However, not much is known about efficient parallel sampling of these structures. Our work is a step towards resolving this mystery. © Nima Anari, Nathan Hu, Amin Saberi, and Aaron Schild.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Combination of parallel Algorithm and Decomposition Projective Method Based on Orthogonal Complement Space 13

Combination of Parallel Algorithm and Decomposition Projecti...

引用

13th International Conference on Microwave and Millimeter Wave Technology, ICMMT 2021

作者： Zhang, Zhanshuo Sun, Lianyou Hong, Wei Southeast University State Key Laboratory Of Millimeter Waves Nanjing210096 China

ISBN: (纸本)9781665434379

In order to improve the computational efficiency of DPM(Decomposition Projective Method) based on orthogonal complement space, this paper has reformed the computing process of the above mothed as a parallel algorithm. All the same kind of subdomains, such as the unchanged subdomains or the optimized subdomains, is designed to be computed parallelly. The algorithm efficiency is verified by a numerical example. The results show that the mothed performs very well. © 2021 IEEE.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Improved MPC algorithms for Edit Distance and Ulam Distance

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 2021年第11期32卷 2764-2776页

作者： Boroujeni, Mahdi Ghodsi, Mohammad Seddighin, Saeed Sharif Univ Technol Dept Comp Engn Tehran *** Iran Inst Res Fundamental Sci Sch Comp Sci Tehran *** Iran Toyota Technol Inst Chicago Chicago IL 60637 USA

Edit distance is one of the most fundamental problems in combinatorial optimization to measure the similarity between strings. Ulam distance is a special case of edit distance where no character is allowed to appear more than once in a string. Recent developments have been very fruitful for obtaining fast and parallel algorithms for both edit distance and Ulam distance. In this work, we present an almost optimal MPC (massively parallel computation) algorithm for Ulam distance and improve MPC algorithms for edit distance. Our algorithm for Ulam distance is almost optimal in the sense that (1) the approximation factor of our algorithm is 1 + epsilon, (2) the round complexity of our algorithm is constant, (3) the total memory of our algorithm is almost linear ((O) over tilde (epsilon)(n)), and (4) the overall running time of our algorithm is almost linear which is the best known for Ulam distance. We also improve the work of Hajiaghayi et al. for edit distance in terms of total memory. The best previously known MPC algorithm for edit distance requires (O) over tilde (n(2x))machines when the memory of each machine is bounded by (O) over tilde (n(1-x)). In this work, we improve the number of machines to (O) over tilde (n((9/5x)) while keeping the memory limit intact. Moreover, the round complexity of our algorithm is constant and the total running time of our algorithm is truly subquadratic. However, our improvement comes at the expense of a constant factor in the approximation guarantee of the algorithm. This improvement is inspired by the recent techniques of Boroujeni et al. and Chakraborty et al. for obtaining truly subquadratic time algorithms for edit distance.

关键词： MapReduce parallel algorithms approximation algorithms ulam distance edit distance

来源：评论

学校读者我要写书评

暂无评论

Comparing Different Approaches for Solving Large Scale Power-Flow Problems With the Newton-Raphson Method

引用

IEEE ACCESS 2021年 9卷 56604-56615页

作者： D'orto, Manolo Sjoblom, Svante Chien, Lung Sheng Axner, Lilit Gong, Jing KTH Royal Inst Technol Sch Elect Engn & Comp Sci PDC Ctr High Performance Comp S-10044 Stockholm Sweden Svenska Kraftnat S-17224 Sundbyberg Sweden NVIDIA Corp Santa Clara CA 95050 USA Uppsala Univ Dept Informat Technol ENCCS S-75105 Uppsala Sweden

This paper focuses on using the Newton-Raphson method to solve the power-fiow problems. Since the most computationally demanding part of the Newton-Raphson method is to solve the linear equations at each iteration, this study investigates different approaches to solve the linear equations on both central processing unit (CPU) and graphical processing unit (GPU). Six different approaches have been developed and evaluated in this paper: two approaches of these run entirely on CPU while other two of these run entirely on GPU, and the remaining two are hybrid approaches that run on both CPU and GPU. All six direct linear solvers use either LU or QR factorization to solve the linear equations. Two different hardware platforms have been used to conduct the experiments. The performance results show that the CPU version with LU factorization gives better performance compared to the GPU version using standard library called cuSOLVER even for the larger power-fiow problems. Moreover, it has been proven that the best performance is achieved using a hybrid method where the Jacobian matrix is assembled on GPU, the preprocessing with a sparse high performance linear solver called KLU is performed on the CPU in the first iteration, and the linear equation is factorized on the GPU and solved on the CPU. Maximum speed up in this study is obtained on the largest case with 25000 buses. The hybrid version shows a speedup factor of 9:6 with a NVIDIA P100 GPU while 13:1 with a NVIDIA V100 GPU in comparison with baseline CPU version on an Intel Xeon Gold 6132 CPU.

关键词： High performance computing Newton method parallel algorithms power engineering computing power-flow direct solver

来源：评论

学校读者我要写书评

暂无评论

Shader-Like Computations in WebGL for Advanced Graphics and General Purposes

引用

COMPUTING IN SCIENCE & ENGINEERING 2021年第2期23卷 54-63页

作者： Watters, Aaron R. Flatiron Inst Comp Core New York NY 10010 USA

The feedWebGL2 software package enables parallel computations using a feature of HTML5/WebGL2 called Transform/Feedback. The Transform/Feedback mechanism can be used within Jupyter widgets or in other web components and applications for a special class of parallel computations called shader-like calculations, which can solve many problems well, but are unsuitable for some classes of parallel algorithms. This article describes the characteristics of shader-like calculations and how they can be created using the feedWebGL2 software package. The example programs use shader-like calculations for special purpose graphical stages in combination with standard WebGL graphics pipelines, and also use them for general purposes, such as matrix computations.

关键词： Internet parallel algorithms Rendering Computer Graphics Software Packages Transform Feedback Matrix Computations Standard Web GL Graphics Pipelines Special Purpose Graphical Stages parallel algorithms Shader Like Calculations Web Components Jupyter Widgets parallel Computations Feed Web GL 2 Software Package General Purposes Advanced Graphics Shader Like Computations Pipelines Isosurfaces Context Modeling Python Image Color Analysis Graphics Processing Units Software Packages

来源：评论

学校读者我要写书评

暂无评论

Fast Hybrid Data Structure for a Large Alphabet K-Mers Indexing for Whole Genome Alignment

引用

IEEE ACCESS 2021年 9卷 161890-161897页

作者： Hrivnak, Rostislav Gajdos, Petr Snasel, Vaclav VSB Tech Univ Ostrava Dept Comp Sci FEECS Ostrava 70800 Czech Republic

The most common index data structures used by whole genome aligners (WGA) are based on suffix trees (ST), suffix arrays, and FM-indexes. These data structures show good performance results as WGA works with sequences of letters over small alphabets;for example, four letters a, c, t, g for DNA alignment. A novel whole genome aligner, which we are developing, will work with distances between the label sites on DNA samples, which are represented as a sequence of positive integers. The size of alphabet sigma is theoretically unlimited. This has prompted us to investigate if there is a better structure that would improve search performance on large alphabets compared to the commonly used suffix-based structures. This paper presents the implementation of a highly optimized hybrid index data structure based on a ternary search tree (TST) and hash tables, which perform much better when working with strings on large alphabets compared to the ST. Single core parallelism was achieved using advanced vector extensions (AVX) single instruction multiple data (SIMD) instruction set. When searching for short k-mers over an alphabet of 25, 695 letters, our index search performance was up to 29 times better than the search performance of the reference ST. When the alphabet was compressed to approximately 1;300 letters, our index search performance was still up to 2.6 times better than the ST. The source code is available free on http://***/Resources/Upload/Home/public/software/*** under the MIT license.

关键词： Engineering management engineering in medicine and biology bioinformatics computational and artificial intelligence computer architecture data structures tree data structures parallel processing parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Interest points reduction using evolutionary algorithms and CBIR for face recognition

引用

VISUAL COMPUTER 2021年第7期37卷 1883-1897页

作者： Villegas-Cortez, Juan Benavides-Alvarez, Cesar Aviles-Cruz, Carlos Roman-Alonso, Graciela de Vega, Francisco Fernandez Chavez, Francisco Cordero-Sanchez, Salomon Univ Autonoma Metropolitana Dept Sistemas Av San Pablo Xalpa 180 Mexico City 02200 DF Mexico Univ Autonoma Metropolitana Dept Elect Av San Pablo Xalpa 180 Mexico City 02200 DF Mexico Univ Autonoma Metropolitana Dept Ingn Elect San Rafael Atlixco 186 Mexico City 09340 DF Mexico Univ Extremadura Dept Comp Sci C Santa Teresa Jornet 38 Merida 06800 Spain Univ Autonoma Metropolitana Dept Quim San Rafael Atlixco 186 Mexico City 09340 DF Mexico

Face recognition has become a fundamental biometric tool that ensures identification of people. Besides a high computational cost, it constitutes an open problem for identifying faces under ideal conditions as well as those under general conditions. Though the advent of high memory and inexpensive computer technologies has made the implementation of face recognition possible in several devices and authentication systems, achieving 100% face recognition in real time is still a challenging task. This paper implements an evolutionary computer genetic algorithm for optimizing the number of interest points on faces, intended to get a quick and precise facial recognition using local analysis texture technique applied to CBIR methodology. Our approach was evaluated using different databases, getting an efficient facial recognition of up to 100% considering only seven interest points from a total of 54 cited in the literature. The interest points reduction was possible through a parallel implementation of our approach using a 54-processor cluster that executes the similar task up to 300% more faster.

关键词： Multi-objective Face recognition parallel algorithms CBIR Genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Integrated Energy and Trust-Based Semi-Markov Prediction for Lifetime Maximization in Wireless Sensor Networks

引用

WIRELESS PERSONAL COMMUNICATIONS 2021年第1期118卷 505-522页

作者： Famila, S. Jawahar, A. Vimalraj, S. Leones Sherwin Lydia, J. SSN Engn Coll Dept Elect & Commun Engn Chennai Tamil Nadu India Panimalar Engn Coll Dept Elect & Commun Engn Chennai Tamil Nadu India Easwari Engn Coll Dept Elect & Elect Engn Chennai Tamil Nadu India

Many of today's computing and communication models are distributed systems that are composed of autonomous computational entities that communicate with each other, usually by passing messages. Distributed systems encompass a variety of applications and wireless sensor networks (WSN) is an important application of it. The tiny, multiple functionality and low power sensor nodes are considered to be interconnected in the WSN for efficient process of aggregating and transmitting the data to the base station. The clustering-based schemes of sensor networks are capable of organizing the network through the utilization of a specifically designated node termed as the cluster head for the objective of energy conservation and data aggregation. Further, the cluster head is responsible for conveying potential information collected by the cluster member nodes and aggregate them before transmitting it to the base station. In this paper, a Reliable Cluster Head Selection Technique using Integrated Energy and Trust-based Semi-Markov Prediction (RCHST-IETSMP) is proposed with the view to extend the lifetime of sensor networks. This proposed RCHST-IETSMP incorporated two significant parameters associated with energy and trust for effective selection of cluster head facilitated through the merits of Semi-Markoc prediction integrated with the Hyper Erlang distribution process. The simulation results of the proposed RCHST-IETSMP scheme is proving to be efficient in upholding the residual energy of the network and the throughput to a maximum level of 23% and 19% predominant to the trust and energy-based clustering schemes considered for investigation.

关键词： Distributed algorithms Clustering Semi-Markov prediction Data aggregation parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Cloud-Ready Acceleration of Formal Method Techniques for Cyber-Physical Systems

IEEE DESIGN & TEST

引用

IEEE DESIGN & TEST 2021年第5期38卷 25-34页

作者： Khaled, Mahmoud Zamani, Majid Tech Univ Munich Munich Germany Univ Colorado Comp Sci Dept Boulder CO USA Ludwig Maximilian Univ Munich Munich Germany

Editor's notes: Controller synthesis using formal specifications has shown considerable promise in recent years. However, it is computationally very expensive. This article shows how cloud computing can come to th... 详细信息

关键词： Kernel Cloud computing parallel algorithms Task analysis Acceleration Copper Formal Methods Cyber-Physical Systems Internet of Things High Performance Computing parallel algorithms Cloud Computing OpenCL Message Passing Interface (MPI) GPGPU FPGA

来源：评论

学校读者我要写书评

暂无评论

Examination of Semi-Analytical Solution Methods in the Coarse Operator of Parareal Algorithm for Power System Simulation

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2021年第6期36卷 5068-5080页

作者： Park, Byungkwon Sun, Kai Dimitrovski, Aleksandar Liu, Yang Simunovic, Srdjan Oak Ridge Natl Lab Computat Sci & Engn Div Oak Ridge TN 37830 USA Univ Cent Florida Dept ECE Orlando FL 32816 USA Univ Tennessee Dept EECS Knoxville TN 37996 USA

With continuing advances in high-performance parallel computing platforms, parallel algorithms have become powerful tools for development of faster than real-time power system dynamic simulations. In particular, it has been demonstrated in recent years that parallel-in-time (Parareal) algorithms have the potential to achieve such an ambitious goal. The selection of a fast and reasonably accurate coarse operator of the Parareal algorithm is crucial for its effective utilization and performance. This paper examines semi-analytical solution (SAS) methods as the coarse operators of the Parareal algorithm and explores performance of the SAS methods to the standard numerical time integration methods. Two promising time-power series-based SAS methods were considered;Adomian decomposition method and Homotopy analysis method with a windowing approach for improving the convergence. Numerical performance case studies on 10-generator 39-bus system and 327-generator 2383-bus system were performed for these coarse operators over different disturbances, evaluating the number of Parareal iterations, computational time, and stability of convergence. All the coarse operators tested with different scenarios have converged to the same corresponding true solution (if they are convergent) and the SAS methods provide comparable computational speed, while having more stable convergence to the true solution in many cases.

关键词： Synthetic aperture sonar Power system stability Power system dynamics Numerical models Mathematical model Heuristic algorithms Computational modeling High-performance computing parallel algorithms power system dynamic simulations semi-analytical solution methods transient stability

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：