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

arXiv 2023年

作者： Wu, Xiaofei Jiang, Jiancheng Zhang, Zhimin College of Mathematics and Statistics Chongqing University China Department of Mathematics and Statistics University of North Carolina at Charlotte United States

The parallel alternating direction method of multipliers (ADMM) algorithms have gained popularity in statistics and machine learning due to their efficient handling of large sample data problems. However, the parallel structure of these algorithms, based on the consensus problem, can lead to an excessive number of auxiliary variables when applied to high-dimensional data, resulting in large computational burden. In this paper, we propose a partition-insensitive parallel framework based on the linearized ADMM (LADMM) algorithm and apply it to solve nonconvex penalized high-dimensional regression problems. Compared to existing parallel ADMM algorithms, our algorithm does not rely on the consensus problem, resulting in a significant reduction in the number of variables that need to be updated at each iteration. It is worth noting that the solution of our algorithm remains largely unchanged regardless of how the total sample is divided, which is known as partition-insensitivity. Furthermore, under some mild assumptions, we prove the convergence of the iterative sequence generated by our parallel algorithm. Numerical experiments on synthetic and real datasets demonstrate the feasibility and validity of the proposed algorithm. We provide a publicly available R software package to facilitate the implementation of the proposed algorithm. Copyright © 2023, The Authors. All rights reserved.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient Modification of the Upper Triangular Square Root Matrix on Variable Reordering

引用

IEEE ROBOTICS AND AUTOMATION LETTERS 2021年第2期6卷 675-682页

作者： Elimelech, Khen Indelman, Vadim Technion Israel Inst Technol Robot & Autonomous Syst Program IL-32000 Haifa Israel Technion Israel Inst Technol Dept Aerosp Engn IL-32000 Haifa Israel

In probabilistic state inference, we seek to estimate the state of an (autonomous) agent from noisy observations. It can be shown that, under certain assumptions, finding the estimate is equivalent to solving a linear least squares problem. Solving such a problem is done by calculating the upper triangularmatrixRfrom the coefficient matrix A, using the QR or Cholesky factorizations;this matrix is commonly referred to as the "square root matrix". In sequential estimation problems, we are often interested in periodic optimization of the state variable order, e.g., to reduce fill-in, or to apply a predictive variable ordering tactic;however, changing the variable order implies expensive re-factorization of the system. Thus, we address the problem of modifying an existing square root matrix R, to convey reordering of the variables. To this end, we identify several conclusions regarding the effect of column permutation on the factorization, to allow efficient modification of R, without accessing A at all, or with minimal re-factorization. The proposed parallelizable algorithm achieves a significant improvement in performance over the state-of-the-art incremental Smoothing AndMapping (iSAM2) algorithm, which utilizes incremental factorization to update R.

关键词： Incremental least squares parallel algorithms probabilistic inference SLAM sparse systems

来源：评论

学校读者我要写书评

暂无评论

Research on parallel algorithm of high-power microwave devices simulation based on MPI-3

引用

AIP ADVANCES 2022年第7期12卷

作者： Hu, Yulan Liu, Dagang Liu, Laqun Wang, Huihui Li, Qiang Univ Elect Sci & Technol China Sch Elect Sci & Engn Chengdu 610054 Peoples R China

Simulation of high-power microwave source devices generally uses parallel algorithms to speed up the operation. In recent years, with the upgrade of parallel technology, the parallel efficiency of the particle simulation software has been further improved. Existing MPI-2 parallel technology of particle simulation software CHIPIC realizes the access to the local memory space of other processes through message passing. The new version of the MPI-3 standard provides the shared memory feature, which allows the data to be directly called by each process in the shared memory window, which reduces the information transmission. In this paper, based on the shared memory feature of MPI-3, the electromagnetic particle simulation parallel algorithm and dynamic load balancing algorithm are designed in the particle simulation software. The implementation of the two algorithms can improve the parallel efficiency from different aspects. The RKA and magnetic isolation oscillator high-power microwave devices are used as the test models. The test results show that the electromagnetic particle simulation parallel algorithm based on the shared memory feature of MPI-3 can improve the efficiency of the software by up to 44%. The efficiency of the dynamic load balancing algorithm based on MPI-3 can also be improved by up to 38%. (c) 2022 Author(s). All article content, except where otherwise noted, is licensed under a Creative Commons Attribution (CC BY) license (http://***/licenses/by/4.0/).

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

PIANO: A fast parallel iterative algorithm for multinomial and sparse multinomial logistic regression

引用

SIGNAL PROCESSING 2022年 194卷

作者： Jyothi, R. Babu, P. Indian Inst Technol Ctr Appl Res Elect Delhi India

Multinomial Logistic Regression is a well-studied tool for classification and has been widely used in fields like image processing, computer vision and, bioinformatics, to name a few. Under a supervised classification scenario, a Multinomial Logistic Regression model learns a weight vector to differentiate between any two classes by optimizing over the likelihood objective. With the advent of big data, the inundation of data has resulted in large dimensional weight vector and has also given rise to a huge number of classes, which makes the classical methods applicable for model estimation not computationally viable. To handle this issue, we here propose a parallel iterative algorithm: parallel Iterative Algorithm for MultiNomial LOgistic Regression ( PIANO ) which is based on the Majorization Minimization procedure, and can parallely update each element of the weight vectors. Further, we also show that PIANO can be easily extended to solve the Sparse Multinomial Logistic Regression problem -an extensively studied problem because of its attractive feature selection property. In particular, we work out the extension of PIANO to solve the Sparse Multinomial Logistic Regression problem with epsilon(1) and t 0 regularizations. We also prove that PIANO converges to a stationary point of the Multinomial and the Sparse Multinomial Logistic Regression problems. Simulations were conducted to compare PIANO with the existing methods, and it was found that the proposed algorithm performs better than the existing methods in terms of speed of convergence.(C) 2022 Elsevier B.V. All rights reserved.

关键词： Multinomial logistic regression Majorization minimization Sparse Parameter estimation Regularization parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

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

引用

OPERATIONS RESEARCH 2021年第5期70卷 iii-vi, 2597-3033, C2-C3页

作者： 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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：