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

IEEE OPEN JOURNAL OF VEHICULAR TECHNOLOGY 2025年 6卷 359-384页

作者： Cong, Pengyu Yang, Chenyang Han, Shengqian Han, Shuangfeng Wang, Xiaoyun Beihang Univ Beijing 100191 Peoples R China China Mobile Res Inst Beijing 100053 Peoples R China

Deep neural networks (DNNs) have been widely used for learning various wireless communication policies. While DNNs have demonstrated the ability to reduce the time complexity of inference, their training often incurs a high computational cost. Since practical wireless systems require retraining due to operating in open and dynamic environments, it is crucial to analyze the factors affecting the training complexity, which can guide the DNN architecture selection and the hyper-parameter tuning for efficient policy learning. As a metric of time complexity, the number of floating-point operations (FLOPs) for inference has been analyzed in the literature. However, the time complexity of training DNNs for learning wireless communication policies has only been evaluated in terms of runtime. In this paper, we introduce the number of serial FLOPs (se-FLOPs) as a new metric of time complexity, accounting for the ability of parallel computing. The se-FLOPs metric is consistent with actual runtime, making it suitable for measuring the time complexity of training DNNs. Since graph neural networks (GNNs) can learn a multitude of wireless communication policies efficiently and their architectures depend on specific policies, no universal GNN architecture is available for analyzing complexities across different policies. Thus, we first use precoder learning as an example to demonstrate the derivation of the numbers of se-FLOPs required to train several DNNs. Then, we compare the results with the se-FLOPs for inference of the DNNs and for executing a popular numerical algorithm, and provide the scaling laws of these complexities with respect to the numbers of antennas and users. Finally, we extend the analyses to the learning of general wireless communication policies. We use simulations to validate the analyses and compare the time complexity of each DNN trained for achieving the best learning performance and achieving an expected performance.

关键词： Training complexity theory Wireless communication time complexity Parallel processing Precoding Measurement time measurement Runtime Hardware DNN parallel computing precoding se-FLOPs time complexity

来源：评论

学校读者我要写书评

暂无评论

Linear time complexity Conformers with SummaryMixing for Streaming Speech Recognition

Linear Time Complexity Conformers with SummaryMixing for Str...

引用

International Conference on Acoustics, Speech, and Signal Processing (ICASSP)

作者： Titouan Parcollet Rogier van Dalen Shucong Zhang Sourav Bhattacharya Samsung AI Center – Cambridge Cambridge United Kingdom

ISBN: (数字)9798350368741

ISBN: (纸本)9798350368758

Automatic speech recognition (ASR) with an encoder equipped with self-attention, whether streaming or non-streaming, takes quadratic time in the length of the speech utterance. This slows down training and decoding, increase the cost, and limits the deployment of the ASR in constrained devices. SummaryMixing is a promising linear-time complexity alternative to self-attention for non-streaming speech recognition that, for the first time, preserves or outperforms the accuracy of self-attention models. Unfortunately, the original definition of SummaryMixing is not suited to streaming speech recognition. Hence, this work extends SummaryMixing to a Conformer Transducer that works in both a streaming and an offline mode. It shows that this new linear-time complexity speech encoder outperforms self-attention in both scenarios while requiring less compute and memory during training and decoding.

关键词： Training Transducers Memory management Graphics processing units Signal processing Real-time systems Decoding complexity theory time complexity Speech processing

来源：评论

学校读者我要写书评

暂无评论

Comparative Analysis of Sorting Algorithms: time complexity and Practical Applications

Comparative Analysis of Sorting Algorithms: Time Complexity ...

引用

Intelligent Data Communication Technologies and Internet of Things (IDCIoT), International Conference on

作者： Manish Rai Hemlata Parmar Suhani Sharma Department of Computer Science and Engineering(AI&ML) Manipal University Jaipur Jaipur India

ISBN: (数字)9798331527549

ISBN: (纸本)9798331527556

In the field of computer science, sorting algorithms are crucial because they facilitate the effective processing and arrangement of data in a variety of scenarios, including data analysis, searching, and optimal system operation. The objective of this study is to look at and compare different sorting algorithms to see how well they work and how useful they are in different situations. The study tests popular sorting algorithms like Quick Sort, Merge Sort, and Bubble Sort on different input sizes, types of data (sorted, reversed, and random), and how they are implemented in the C++ programming language. The study shows how they work in terms of time complexity, resource use, and real applications through a systematic analysis. The most important results show that algorithms work differently depending on the inputs. For example, Quick Sort does better in most situations, while Merge Sort stays stable in the worst ones. This work also finds situations where simpler algorithms, like Bubble Sort, are good for small data sets. This paper is unique because it gives real-life cases, suggestions for choosing the best algorithm based on specific needs, and suggestions for how to do that. The goal of these results is to help programmers, teachers, and experts pick the right sorting algorithms for their computer tasks.

关键词： Machine learning algorithms Data analysis Systematics Systems operation Instruction sets Machine learning Internet of Things time complexity Optimization Sorting

来源：评论

学校读者我要写书评

暂无评论

time complexity Analysis of an Evolutionary Algorithm for Finding Nearly Maximum Cardinality Matching

引用

Journal of Computer Science & Technology 2004年第4期19卷 450-458页

作者： JunHe XinYao StateKeyLabofSoftwareEngineering WuhanUniversityWuhan430072P.R.China SchoolofComputerScience UniversityofBirminghamBirminghamB152TTEnglandU.K.

Most of works on the time complexity analysis of evolutionary algorithms havealways focused on some artificial binary problems. The time complexity of the algorithms forcombinatorial optimisation has not been well understood. This paper considers the time complexity ofan evolutionary algorithm for a classical combinatorial optimisation problem, to find the maximumcardinality matching in a graph. It is shown that the evolutionary algorithm can produce a matchingwith nearly maximum cardinality in average polynomial time.

关键词： evolutionary algorithm (EA) combinatorial optimisation time complexity maximum matching

来源：评论

学校读者我要写书评

暂无评论

time complexity of Link Reversal Routing

引用

ACM TRANSACTIONS ON ALGORITHMS 2015年第3期11卷 1–39页

作者： Charron-Bost, Bernadette Fuegger, Matthias Welch, Jennifer L. Widder, Josef Ecole Polytech LIX Lab Informat F-91128 Palaiseau France TU Wien Dept Comp Engn A-1040 Vienna Austria Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA TU Wien A-1040 Vienna Austria

Link reversal is a versatile algorithm design paradigm, originally proposed by Gafni and Bertsekas in 1981 for routing and subsequently applied to other problems including mutual exclusion, leader election, and resource allocation. Although these algorithms are well known, until now there have been only preliminary results on time complexity, even for the simplest link reversal algorithm for routing, called Full Reversal. In Full Reversal, a sink reverses all its incident links, whereas in other link reversal algorithms (e.g., Partial Reversal), a sink reverses only some of its incident links. Charron-Bost et al. introduced a generalization, called LR, that includes Full and Partial Reversal as special cases. In this article, we present an exact expression for the time complexity of LR. The expression is stated in terms of simple properties of the initial graph. The result specializes to exact formulas for the time complexity of any node in any initial acyclic directed graph for both Full and Partial Reversal. Having the exact formulas provides insight into the behavior of Full and Partial Reversal on specific graph families. Our first technical insight is to describe the behavior of Full Reversal as a dynamical system and to observe that this system is linear in min-plus algebra. Our second technical insight is to overcome the difficulty posed by the fact that LR is not linear by transforming every execution of LR from an initial graph into an execution of Full Reversal from a different initial graph while maintaining the execution's work and time complexity.

关键词： Routing link reversal time complexity linear dynamical systems min-plus algebra

来源：评论

学校读者我要写书评

暂无评论

time complexity of iterative-deepening-A*

引用

ARTIFICIAL INTELLIGENCE 2001年第1-2期129卷 199-218页

作者： Korf, RE Reid, M Edelkamp, S Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA Univ Massachusetts Dept Math & Stat Amherst MA 01003 USA Inst Informat D-79110 Freiburg Germany

We analyze the time complexity of iterative-deepening-A* (IDA*). We first show how to calculate the exact number of nodes at a given depth of a regular search tree, and the asymptotic brute-ford branching factor. We then use this result to analyze IDA* with a consistent, admissible heuristic function. Previous analyses relied on an abstract analytic model, and characterized the heuristic function in terms of its accuracy, but do not apply to concrete problems. In contrast, our analysis allows us to accurately predict the performance of IDA* on actual problems such as the sliding-tile puzzles and Rubik's Cube. The heuristic function is characterized by the distribution of heuristic values over the problem space. Contrary to conventional wisdom, our analysis shows that the asymptotic heuristic branching factor is the same as the brute-force branching factor. Thus, the effect of a heuristic function is to reduce the effective depth of search by a constant, relative to a brute-force search, rather than reducing the effective branching factor. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： problem solving heuristic search iterative-deepening-A* time complexity branching factor heuristic branching factor sliding-tile puzzles eight puzzle fifteen puzzle Rubik's cube

来源：评论

学校读者我要写书评

暂无评论

time complexity of single- and identical parallel-machine scheduling with GERT network precedence constraints

引用

MATHEMATICAL METHODS OF OPERATIONS RESEARCH 1999年第2期49卷 221-238页

作者： Zimmermann, J Univ Karlsruhe Inst Wirtschaftstheorie & Operat Res D-76128 Karlsruhe Germany

In this paper we deal with the time complexity of single- and identical parallel-machine scheduling problems in which the durations and precedence constraints of the activities are stochastic. The stochastic precedence constraints are given by GERT networks. First, we sketch the basic concepts of GERT networks and machine scheduling with GERT network precedence constraints. Second, we discuss the time complexity of some open single-machine scheduling problems with GERT network precedence constraints. Third, we investigate the time complexity of identical parallel-machine scheduling problems with GERT network precedence constraints. Finally, we present an efficient reduction algorithm for the problem of computing the expected makespan for the latter type of scheduling problem.

关键词： stochastic scheduling single machine identical parallel machines GERT networks time complexity

来源：评论

学校读者我要写书评

暂无评论

time complexity and model complexity of fast identification of continuous-time LTI systems

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 1999年第10期44卷 1814-1828页

作者： Lin, L Wang, LY Zames, G MPD Technol Inc Hauppauge NY 11788 USA Wayne State Univ Dept Elect & Comp Engn Detroit MI 48202 USA

The problem of fast identification of continuous-time systems is formulated in the metric complexity theory setting. It is shown that the two key steps to achieving fast identification, i.e., optimal input design and optimal model selection, can be carried out independently when the true system belongs to a general a priori set. These two optimization problems can be reduced to standard Gel'fand and Kolmogorov n-width problems in metric complexity theory. It is shown that although arbitrarily accurate identification can be achieved on a small time interval by reducing the noise-signal ratio and designing the input carefully, identification speed is limited by the metric complexity of the a priori uncertainty set when the noise/signal ratio is fixed.

关键词： adaptive control H-infinity identification model complexity time complexity

来源：评论

学校读者我要写书评

暂无评论

time complexity of In-Memory Solution of Linear Systems

引用

IEEE TRANSACTIONS ON ELECTRON DEVICES 2020年第7期67卷 2945-2951页

作者： Sun, Zhong Pedretti, Giacomo Mannocci, Piergiulio Ambrosi, Elia Bricalli, Alessandro Ielmini, Daniele Politecn Milan Dipartimento Elettron Informaz & Bioingn I-20133 Milan Italy

In-memory computing (IMC) with cross-point resistive memory arrays has been shown to accelerate data-centric computations, such as the training and inference of deep neural networks, due to the high parallelism endowed by physical rules in the electrical circuits. By connecting cross-point arrays with negative feedback amplifiers, it is possible to solve linear algebraic problems, such as linear systems and matrix eigenvectors in just one step. Based on the theory of feedback circuits, we study the dynamics of the solution of linear systems within a memory array, showing that the time complexity of the solution is free of any direct dependence on the problem size N, rather it is governed by theminimal eigenvalue of an associatedmatrix of the coefficient matrix. We show that when the linear system is modeled by a covariancematrix, the time complexity is O(logN) or O(1). In the case of sparse positive-definite linear systems, the time complexity is solely determined by the minimal eigenvalue of the coefficient matrix. These results demonstrate the high speed of the circuit for solving linear systems in a wide range of applications, thus supporting IMC as a strong candidate for future big data and machine learning accelerators.

关键词： In-memory computing (IMC) linear system resistive memory time complexity

来源：评论

学校读者我要写书评

暂无评论

time complexity of In-Memory Matrix-Vector Multiplication

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS 2021年第8期68卷 2785-2789页

作者： Sun, Zhong Huang, Ru Peking Univ Inst Artificial Intelligence Beijing 100871 Peoples R China Peking Univ Inst Microelect Beijing 100871 Peoples R China

Matrix-vector multiplication (MVM) is the core operation of many important algorithms. Crosspoint resistive memory array enables naturally calculating MVM in one operation, thus representing a highly promising computing accelerator for various applications. To evaluate computing performance as well as scalability of in-memory MVM, the fundamental issue of time complexity of the circuit shall be elaborated. Based on the most common MVM circuit that uses transimpedance amplifiers to read out current product in crosspoint array, we analyze its dynamic response and the corresponding time complexity. The result shows that the computing time is governed by the maximal row sum of the implemented matrix, which leads to an explicit time complexity for a specific dataset, e.g., O(N-1/2) and O(lnN) for discrete cosine transformation and Toeplitz matrix, respectively. By changing accordingly feedback conductance of transimpedance amplifier for different matrix sizes, it is possible to reduce the time complexity to O(1). Impact of non-ideal factors of the circuit on computing time is also studied. This work provides an insight into the performance and its improvement of MVM computation for efficient in-memory computing accelerators.

关键词： In-memory computing time complexity matrix-vector multiplication resistive memory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：