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

Temporal parallelization of Bayesian Smoothers

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2021年第1期66卷 299-306页

作者： Sarkka, Simo Garcia-Fernandez, Angel F. Aalto Univ Dept Elect Engn & Automat Espoo 02150 Finland Univ Liverpool Dept Elect Engn & Elect Liverpool L69 3GJ Merseyside England

This article presents algorithms for temporal parallelization of Bayesian smoothers. We define the elements and the operators to pose these problems as the solutions to all-prefix-sums operations for which efficient parallel scan-algorithms are available. We present the temporal parallelization of the general Bayesian filtering and smoothing equations, and specialize them to linear/Gaussian models. The advantage of the proposed algorithms is that they reduce the linear complexity of standard smoothing algorithms with respect to time to logarithmic.

关键词： Bayes methods Smoothing methods Mathematical model Computational modeling Kalman filters parallel algorithms Bayesian smoothing Kalman filtering and smoothing parallel computing parallel scan prefix sums

来源：评论

学校读者我要写书评

暂无评论

An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model

引用

OPERATIONS RESEARCH 2021年第5期70卷 2967页

作者： Balkanski, Eric Rubinstein, Aviad Singer, Yaron Columbia Univ Dept Ind Engn & Operat Res New York NY 10027 USA Stanford Univ Dept Comp Sci Stanford CA 94305 USA Harvard Univ Sch Engn & Appl Sci Cambridge MA 02138 USA

In this paper, we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimization to quantify the information theoretic complexity of black-box optimization in a parallel computation model. Despite the burst in work on submodular maximization in the adaptive complexity model, the fundamental problem of maximizing a monotone submodular function under a matroid constraint has remained elusive. In particular, all known techniques fail for this problem and there are no known constant factor approximation algorithms whose adaptivity is sublinear in the rank of the matroid k or in the worst case sublinear in the size of the ground set n. We present an algorithm that has an approximation guarantee arbitrarily close to the optimal 1 - 1/e for monotone submodular maximization under a matroid constraint and has near-optimal adaptivity of O(log (n) log (k)). This result is obtained using a novel technique of adaptive sequencing, which departs from previous techniques for submodular maximization in the adaptive complexity model. In addition to our main result, we show how to use this technique to design other approximation algorithms with strong approximation guarantees and polylogarithmic adaptivity.

关键词： submodular optimization parallel algorithms matroids adaptivity

来源：评论

学校读者我要写书评

暂无评论

Real-Time Computation of 3D Wireframes in Computer-Generated Holography

引用

IEEE TRANSACTIONS ON IMAGE PROCESSING 2021年 30卷 9418-9428页

作者： Blinder, David Nishitsuji, Takashi Schelkens, Peter Vrije Univ Brussel VUB Dept Elect & Informat ETRO B-1050 Brussels Belgium IMEC B-3001 Leuven Belgium Tokyo Metropolitan Univ Fac Syst Design Hino Tokyo 1910065 Japan

Computer-Generated Holography (CGH) algorithms simulate numerical diffraction, being applied in particular for holographic display technology. Due to the wave-based nature of diffraction, CGH is highly computationally intensive, making it especially challenging for driving high-resolution displays in real-time. To this end, we propose a technique for efficiently calculating holograms of 3D line segments. We express the solutions analytically and devise an efficiently computable approximation suitable for massively parallel computing architectures. The algorithms are implemented on a GPU (with CUDA), and we obtain a 70-fold speedup over the reference point-wise algorithm with almost imperceptible quality loss. We report real-time frame rates for CGH of complex 3D line-drawn objects, and validate the algorithm in both a simulation environment as well as on a holographic display setup.

关键词： Three-dimensional displays Holography Diffraction Real-time systems Optical diffraction Streaming media Holographic optical components Holography diffraction computer graphics displays approximation methods parallel algorithms optical devices physics computing

来源：评论

学校读者我要写书评

暂无评论

A parallel Robin-Robin Domain Decomposition Method based on Modified Characteristic FEMs for the Time-Dependent Dual-porosity-Navier-Stokes Model with the Beavers-Joseph Interface Condition

引用

JOURNAL OF SCIENTIFIC COMPUTING 2022年第1期90卷 16-16页

作者： Cao, Luling He, Yinnian Li, Jian Xi An Jiao Tong Univ Sch Math & Stat Xian 710049 Peoples R China Shaanxi Univ Sci & Technol Dept Math Xian 710021 Peoples R China

In this paper, we propose and analyze the parallel Robin-Robin domain decomposition method based on the modified characteristic finite element method for the time-dependent dual-porosity-Navier-Stokes model with the Beavers-Joseph interface condition. For the coupling terms, we treat them in an explicit manner which takes advantage of information obtained in previous time steps to construct a non-iteration domain decomposition method. By this means, two single dual-porosity equations and a single Navier-Stokes equation are needed to solve at each time. In particular, we solve the Navier-Stokes equation by the modified characteristic finite element method, which avoids the computational inefficiency caused by the nonlinear convection term. Furthermore, we prove the error convergence of solutions by mathematical induction, whose proof implies the uniform L-infinity-boundedness of the fully discrete velocity solution in conduit flow. Finally, some numerical examples are presented to show the effectiveness and efficiency of the proposed method.

关键词： Time-dependent dual-porosity-Navier-Stokes model Beavers-Joseph interface condition Domain decomposition methods Modified characteristic finite element methods parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Synchronous parallel Block Coordinate Descent Method for Nonsmooth Convex Function Minimization

引用

Journal of Systems Science & Complexity 2020年第2期33卷 345-365页

作者： DAI Yutong WENG Yang College of Mathematics Sichuan UniversityChengdu 610064China

This paper proposes a synchronous parallel block coordinate descent algorithm for minimizing a composite function,which consists of a smooth convex function plus a non-smooth but separable convex *** to the generalization of the proposed method,some existing synchronous parallel algorithms can be considered as special *** tackle high dimensional problems,the authors further develop a randomized variant,which randomly update some blocks of coordinates at each round of *** proposed parallel algorithms are proven to have sub-linear convergence rate under rather mild *** numerical experiments on solving the large scale regularized logistic regression with 1 norm penalty show that the implementation is quite *** authors conclude with explanation on the observed experimental results and discussion on the potential improvements.

关键词： Block coordinate descent convergence rate convex functions parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A parallel algorithm for Delaunay triangulation of moving points on the plane

arXiv

引用

arXiv 2023年

作者： Hadiniya, Nazanin Ghodsi, Mohammad Computer Engineering Department Sharif University of Technology Tehran Iran

Delaunay Triangulation(DT) is one of the important geometric problems that is used in various branches of knowledge such as computer vision, terrain modeling, spatial clustering and networking. Kinetic data structures has become very important in computational geometry for dealing with moving objects. However, when dealing with moving points, maintaining a dynamically changing Delaunay triangulation can be challenging. So, In this case, we have to update triangulation repeatedly. If the points move so far, it’s better to rebuild the triangulation. One approach to handle moving points is to use an incremental algorithm. For the case that points move slowly, we can give a faster algorithm than rebuilding. Furthermore, sequential algorithms can be computationally expensive for large datasets. So one way to compute as fast as possible is parallelism. In this paper, we propose a parallel algorithm for moving points. we propose an algorithm that divides datasets into equal partitions and give every partition to one block. Each block satisfay the Delaunay constraints after each time step and uses delete and insert algorithms to do this. We show this algorithm works faster than serial algorithms. Copyright © 2023, The Authors. All rights reserved.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Image defogging based on amended dark channel prior and 4-directional L₁ regularisation

引用

IET IMAGE PROCESSING 2021年第11期15卷 2454-2477页

作者： Yang, Yuliang Long, Wei Li, Yanyan Shi, Xiaoqiu Gao, Lin Sichuan Univ Sch Mech Engn Yihuan Rd Chengdu 610065 Peoples R China Shaanxi Inst Technol 8 Renmin Rd Huyi Dist Xian Peoples R China Southwest Univ Sci & Technol Sch Mfg Sci & Engn Mianyang Sichuan Peoples R China Hubei Minzu Univ Sch Informat Engn Enshi Peoples R China

The dark channel prior (DCP) algorithm has been widely used in the field of image defogging because of its simple theory and clear restoration result. However, the DCP algorithm has significant limitations. This study clarifies the relationship between halo artfacts and the size of the dark channel patch of the DCP algorithm and analyses the reason why the colour of close-range white objects appears distorted in the restored images. An amended DCP method is then proposed to solve these problems, utilising a locally variable weighted 4-directional L-1 regularisation and a corresponding parallel algorithm to optimise the transmission. A deep neural network, 4DL(1)R-net, is then trained to further enhance the processing speed. Extensive experiments demonstrate that this method is effective. The proposed method can obtain clear details, maintain the natural clarity of images, and achieve significant improvements over state-of-the-art methods.

关键词： close-range white objects dark channel prior Computer vision and image processing techniques images restored image colour analysis image restoration DCP algorithm parallel algorithms 4-directional L1 regularisation deep neural network Optical, image and video signal processing image defogging image enhancement 4DL1R-net deep learning (artificial intelligence) parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Sampling arborescences in parallel 12

Sampling arborescences in parallel

引用

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

On parallel Calculation of All-Terminal Network Reliability 17

On Parallel Calculation of All-Terminal Network Reliability

引用

17th International Asian School-Seminar "Optimization Problems of Complex Systems", OPCS 2021

作者： Sergeev, Kirill Migov, Denis Novosibirsk State University Novosibirsk Russia Institute of Computational Mathematics and Mathematical Geophysics SB RAS Novosibirsk Russia

ISBN: (纸本)9781665405621

The paper presents parallel algorithms for calculating the exact value of all-terminal reliability of a network with unreliable edges and absolutely reliable nodes. A random graph is used as a model of such network. The algorithms are based on the factorization procedure which is a well-known sequential method of a reliability calculation. parallelization of the algorithms consists in sending subgraphs, arising during the factorization of a network on the master process, to the rest of the processes that perform sequential calculation by the factorization. The basic idea of the parallel algorithms proposed is to distinguish those subgraphs, arising during the factorization in the work processes, that are relatively hard for reliability calculation. These subgraphs are sent back to the master process, which runs the computation of their reliability in a recursive way, i.e. according to the same scheme as with an initial graph. The results of the numerical experiments are given. © 2021 IEEE

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：