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

arXiv 2023年

作者： Wu, Xiaofei Zhang, Zhimin Cui, Zhenyu College of Mathematics and Statistics Chongqing University Chongqing401331 China School of Business Stevens Institute of Technology HobokenNJ07030 United States

The parallel alternating direction method of multipliers (ADMM) algorithm is widely recognized for its effectiveness in handling large-scale datasets stored in a distributed manner, making it a popular choice for solving statistical learning models. However, there is currently limited research on parallel algorithms specifically designed for high-dimensional regression with combined (composite) regularization terms. These terms, such as elastic-net, sparse group lasso, sparse fused lasso, and their nonconvex variants, have gained significant attention in various fields due to their ability to incorporate prior information and promote sparsity within specific groups or fused variables. The scarcity of parallel algorithms for combined regularizations can be attributed to the inherent nonsmoothness and complexity of these terms, as well as the absence of closed-form solutions for certain proximal operators associated with them. In this paper, we propose a unified constrained optimization formulation based on the consensus problem for these types of convex and nonconvex regression problems and derive the corresponding parallel ADMM algorithms. Furthermore, we prove that the proposed algorithm not only has global convergence but also exhibits linear convergence rate. Extensive simulation experiments, along with a financial example, serve to demonstrate the reliability, stability, and scalability of our algorithm. The R package for implementing the proposed algorithms can be obtained at https://***/xfwu1016/CPADMM. Copyright © 2023, The Authors. All rights reserved.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Data-centric workloads with MPI_Sort

引用

JOURNAL OF parallel AND DISTRIBUTED COMPUTING 2024年 187卷

作者： Zulian, P. Ben Bader, S. Fourestey, G. Krause, R. Rossinelli, D. Univ Svizzera Italiana Euler Inst Fac informat Lugano Switzerland Swiss Fed Inst Technol Lausanne Switzerland UniDistance Brig Switzerland Stanford Univ Inst Computat Math Engn Stanford CA 94305 USA

Sorting is a fundamental task in computing and plays a central role in information technology. The advent of rack-scale and warehouse-size data processing shaped the architecture of data analysis platforms towards supercomputing. In turn, established techniques on supercomputers have become relevant to a wider range of application domains. This work is concerned with multi-way mergesort with exact splitting on distributed memory architectures. At its core, our approach leverages a novel and parallel algorithm for multi-way selection problems. Remarkably concise, the algorithm relies on MPI_Allgather and MPI_ReduceScatter_block, two collective communication schemes that find hardware support in most high-end networks. A software implementation of our approach is used to process the Terabyte-size Data Challenge 2 signal, released by the SKA radio telescopes organization. On the supercomputer considered herein, our approach outperforms the state of the art by up to 2.6X using 9,216 cores. Our implementation is released as a compact open source library compliant to the MPI programming model. By supporting the most popular elementary key types, and arbitrary fixed-size value types, the library can be straightforwardly integrated into third-party MPI-based software

关键词： Distributed sorting parallel algorithms Supercomputers

来源：评论

学校读者我要写书评

暂无评论

Partition-Insensitive parallel ADMM Algorithm for High-dimensional Linear Models

arXiv

引用

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

来源：评论

学校读者我要写书评

暂无评论

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

引用

SIGNAL PROCESSING 2022年 194卷 108459-108459页

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：