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

2nd International Conference on Mathematics and Computers in Science and Engineering (MACISE)

作者： Jirina, Marcel Inst Comp Sci AS CR Dept Machine Learning Prague Czech Republic

ISBN: (纸本)9781728166957

Sorting with real number keys has time complexity n log n. This holds under the assumption that for all n samples a comparison sort is used. Here we propose to use the counting sort with just n cells for initial placement of samples. We resolve cases of groups of several samples placed into one cell by a comparison sort. Surprisingly, even this part has time complexity proportional to n. Numerical experiments confirm this finding and shows influence of the computing environment such as paging, and reflects a higher speed than the quicksort.

关键词： sorting algorithm sorting reals linear time complexity countingsort

来源：评论

学校读者我要写书评

暂无评论

linear time manageable edge-aware filtering on complementary tree structures

引用

COMPUTERS & GRAPHICS-UK 2024年 118卷 133-145页

作者： Bu, Penghui Wang, Hang Yang, Tao Zhao, Hong Xian Shiyou Univ Sch Mech Engn 18Elect Second Rd Xian 710065 Shaanxi Peoples R China Xian Chishine Optoelect Technol Co 69 Jin Ye Rd Xian 710076 Shaanxi Peoples R China Xi An Jiao Tong Univ State Key Lab Mfg Syst Engn 28 Xianning West Rd Xian 710049 Shaanxi Peoples R China

Typical non-local edge-aware filtering methods build long-range connections by deriving a minimum spanning tree (MST) from the input image. Each pixel on the MST only connects to a sub-set of pixels in the 8-connected neighborhood, resulting in piece-wise constant output with fake edges among sub-trees for the unbalanced information propagation along eight directions. In this paper, we propose two complementary spatial trees to incorporate information from the entire image. The structure of each tree depends on the spatial relationships of neighboring pixels. The distances between any two pixels in both spatial space and intensity space are the shortest distances on each tree. We introduce an efficient algorithm to recursively compute the output and the normalization constant on each tree with linear time complexity. For each pixel, we first calculate the outputs from eight subtrees and then fuse them to obtain the result on each tree structure. The final filtering output of our method is the weighted average of the results from two complementary spatial trees. Moreover, we present a distance mapping scheme to adjust the intensity distance between neighboring pixels, enabling our method to filter out a manageable degree of low-amplitude structures while sharpening major edges. Extensive experiments in graphic applications, such as image denoising, JPEG artifact removal, tone mapping, detail enhancement, and colorization, demonstrate the effectiveness and versatility of our method.

关键词： Non-local edge-aware filtering Complementary trees linear time complexity Distance mapping Spatial relationship Manageable smoothing

来源：评论

学校读者我要写书评

暂无评论

Hybrid Stochastic Computing of linear time O(N) and Its In-Memory Computing for High Performances

Hybrid Stochastic Computing of Linear Time O(N) and Its In-M...

引用

IEEE-Computer-Society Annual Symposium on VLSI (ISVLSI)

作者： Chen, Yuhao Li, Hongge Song, Yinjie Zhu, Xinyu Beihang Univ Coll Elect Informat Engn Beijing Peoples R China

ISBN: (纸本)9798350354119

Stochastic computing (SC) reduces the complexity of arithmetic circuits but brings extra conversion cost and time complexity of O(2(N)), which leads to a much lower efficiency than binary. This paper proposes a linear-time, O(N), and conversionfree hybrid stochastic computing (HSC). Moreover, a hybrid stochastic computing in-memory method is proposed, mapping addition and multiplication of HSC into memory's enable and addressing circuits. Thus, the basic memory having enable and addressing circuits can realize HSC operation without additional circuits. The experiment shows that HSC in block memory (BRAM) based on FPGA for matrix multiplication reaches 2.304 TOPS (operation per second) and 17.2 TOPS/***. Each 18K-BRAM provides 18 GOPS (INT8) with 8.34 mW at 600 MHz.

关键词： Hybrid stochastic computing linear time complexity Computing in memory High performance

来源：评论

学校读者我要写书评

暂无评论

Optimal multilevel adaptive FEM for the Argyris element

引用

COMPUTER METHODS IN APPLIED MECHANICS AND ENGINEERING 2022年 399卷 1页

作者： Graessle, Benedikt Humboldt Univ Inst Math D-10117 Berlin Germany

The main drawback for the application of the conforming Argyris FEM is the labourious implementation on the one hand and the low convergence rates on the other. If no appropriate adaptive meshes are utilised, only the convergence rate caused by corner singularities (Blum and Rannacher, 1980), far below the approximation order for smooth functions, can be achieved. The fine approximation with the Argyris FEM produces high-dimensional linear systems and for a long time an optimal preconditioned scheme was not available for unstructured grids. This paper presents numerical benchmarks to confirm that the adaptive multilevel solver for the hierarchical Argyris FEM from Carstensen and Hu (2021) is in fact highly efficient and of linear time complexity. Moreover, the very first display of optimal convergence rates in practically relevant benchmarks with corner singularities and general boundary conditions leads to the rehabilitation of the Argyris finite element from the computational perspective. (c) 2022 Elsevier B.V. All rights reserved.

关键词： A posteriori Adaptive algorithm Argyris element Optimal convergence Multilevel preconditioning linear time complexity

来源：评论

学校读者我要写书评

暂无评论

Singe Image Dehazing With Unsharp Masking and Color Gamut Expansion

引用

IEEE ACCESS 2022年 10卷 102462-102474页

作者： Ngo, Dat Lee, Gi-Dong Kang, Bongsoon Tech Support & Dev Ctr Display Device Convergence Busan 49315 South Korea Dong A Univ Dept Elect Engn Busan 49315 South Korea

Image dehazing is a fundamental problem in computer vision and has hitherto engendered prodigious amounts of studies. Recently, with the well-recognized success of deep learning techniques, this field has been dominated by deep dehazing models. However, deep learning is not always a panacea, especially for the practicalities of image dehazing, because high computational complexity, expensive maintenance costs, and high carbon emission are three noticeable problems. Computational efficiency is, therefore, a decisive factor in real-world circumstances. To cope with this growing demand, we propose a linear time algorithm tailored to three primitive parts: unsharp masking (pre-processing), dehazing, and color gamut expansion (post-processing). The first enhances the sharpness according to the local variance of image intensities. The second removes haze based on the improved color attenuation prior, and the third addresses a residual effect of color gamut reduction. Extensive experimental results demonstrated that the proposed method performed comparatively with popular benchmarks, notably deep dehazing models. With such a comparative performance, the proposed method is still fast and efficient, favoring real-world computer vision systems.

关键词： Image color analysis Deep learning Scattering Atmospheric modeling Degradation Cameras Image dehazing unsharp masking color gamut expansion linear time complexity

来源：评论

学校读者我要写书评

暂无评论

The generalized trust region subproblem: solution complexity and convex hull results

引用

MATHEMATICAL PROGRAMMING 2022年第2期191卷 445-486页

作者： Wang, Alex L. Kilinc-Karzan, Fatma Carnegie Mellon Univ Pittsburgh PA 15213 USA

We consider the generalized trust region subproblem (GTRS) ofminimizing a nonconvex quadratic objective over a nonconvex quadratic constraint. Alifting of this problem recasts the GTRS as minimizing a linear objective subject to two nonconvex quadratic constraints. Our first main contribution is structural: we give an explicit description of the convex hull of this nonconvex set in terms of the generalized eigenvalues of an associated matrix pencil. This result may be of interest in building relaxations for nonconvex quadratic programs. Moreover, this result allows us to reformulate the GTRS as the minimization of two convex quadratic functions in the original space. Our next set of contributions is algorithmic: we present an algorithm for solving the GTRS up to an epsilon additive error based on this reformulation. We carefully handle numerical issues that arise from inexact generalized eigenvalue and eigenvector computations and establish explicit running time guarantees for these algorithms. Notably, our algorithms run in linear (in the size of the input) time. Furthermore, our algorithm for computing an epsilon-optimal solution has a slightly-improved running time dependence on epsilon over the state-of-the-art algorithm. Our analysis shows that the dominant cost in solving the GTRS lies in solving a generalized eigenvalue problem-establishing a natural connection between these problems. Finally, generalizations of our convex hull results allow us to apply our algorithms and their theoretical guarantees directly to equality-, interval-, and hollow-constrained variants of the GTRS. This gives the first linear-time algorithm in the literature for these variants of the GTRS.

关键词： Generalized trust region subproblem Convex hull linear time complexity

来源：评论

学校读者我要写书评

暂无评论

linear time algorithms on mirror trees

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第5期44卷 3495-3519页

作者： Quilliot, Alain Rebaine, Djamal Univ Clermont Auvergne Labex IMOBS3 LIMOS UMR CNRS 6158 Clermont Ferrand France Univ Quebec Chicoutimi Dept Informat & Math Chicoutimi PQ Canada

We address in this paper two problems on mirror graphs. The first is the recognition problem. While it is graph isomorphism complete, we show the analogous problem of recognizing mirror trees is solvable in linear time. The second problem we are tackling in this study is the linear ordering problem on mirror trees with respect to Directed Sum-Cut cost criterion for which a linear time algorithm is exhibited.

关键词： Mirror graphs Mirror trees Directed sum-cut linear ordering linear time complexity

来源：评论

学校读者我要写书评

暂无评论

A note on the linearity of Ratliff and Rosenthal's algorithm for optimal picker routing

引用

OPERATIONS RESEARCH LETTERS 2022年第2期50卷 155-159页

作者： Hessler, Katrin Irnich, Stefan Johannes Gutenberg Univ Mainz Gutenberg Sch Management & Econ Chair Logist Management Jakob Welder Weg 9 D-55128 Mainz Germany

Ratliff and Rosenthal state that their dynamic programming algorithm for optimal picker routing has linear complexity in the number of aisles. Indeed, solving the dynamic program is linear, but computing the cost coefficients of the dynamic program certainly requires the consideration of all picking positions, whose number is independent of the number of aisles. For a given unsorted sequence of picking positions, our algorithm is linear in the sum of the number of aisles and number of picking positions. (C) 2022 Elsevier B.V. All rights reserved.

关键词： Picker routing problem Dynamic programming linear time complexity Maximum gap problem

来源：评论

学校读者我要写书评

暂无评论

BaW 1.0-A Problem Specific SAT Solver for Effective Strong Connectivity Testing in Sparse Directed Graphs 18

BaW 1.0-A Problem Specific SAT Solver for Effective Strong C...

引用

18th IEEE International Symposium on Computational Intelligence and Informatics (CINTI)

作者： Biro, Csaba Kusper, Gabor Eszterhazy Karoly Univ Inst Math & Informat Eger Hungary

ISBN: (纸本)9781728111179

In our previous works, we proved that if a directed graph is strongly connected, then the generated 2-SAT problem is a black-and-white 2-SAT problem, which has two solutions: where each variable is true (the white assignment), and where each variable is false (the black one). We proved also theoretically that these problems could be solved in linear time. In this article we present a DPLL-based problem specific SAT solver called BaW 1.0. Problem specific, because the BaW 1.0 is not a complete SAT solver, it is only validated for our special black-and-white 2-SAT problem based benchmarks. First, we show how to solve the black-and-white 2-SAT problems in linear time and how to use this solver for effective strong connectivity testing in large and sparse directed graphs. After that we present our results on these benchmarks which show that remarkable improvements have taken place in the number of solved instances as well as in the computation time compared to existing modern State-of-the-art SAT solvers (CSFLOC 8, Glucose 3.0).

关键词： BaW 1.0-a problem specific SAT solver black-and-white 2-SAT problem directed graph 2-SAT problem strong connectivity linear time complexity

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm for the trust region subproblem based on hidden convexity

引用

OPTIMIZATION LETTERS 2017年第8期11卷 1639-1646页

作者： Wang, Jiulin Xia, Yong Beihang Univ State Key Lab Software Dev Environm LMIB Minist EducSch Math & Syst Sci Beijing 100191 Peoples R China

We present a linear-time approximation scheme for solving the trust region subproblem (TRS). It employs Nesterov's accelerated gradient descent algorithm to solve a convex programming reformulation of (TRS). The total time complexity is less than that of the recent linear-time algorithm. The algorithm is further extended to the two-sided trust region subproblem.

关键词： Trust region subproblem Hidden convexity Proximal gradient algorithm linear time complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：