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

algebraic algorithms for multiloop calculations - The first 15 years. What's next?

NUCLEAR INSTRUMENTS & METHODS IN PHYSICS RESEARCH SECTION A-ACCELERATORS SPECTROMETERS DETECTORS AND ASSOCIATED EQUIPMENT 1997年第1-2期389卷 309-313页

作者： Tkachov, FV Institute for Nuclear Research of Russian Academy of Sciences INR RAS Moscow 117312 Russia

The ideas behind the concept of algebraic (''integration-by-parts'') algorithms for multiloop calculations are reviewed. For any topology and mass pattern, a finite iterative algebraic procedure is proved to exist which transforms the corresponding Feynman-parametrized integrands into a form that is optimal for numerical integration, with all the poles in D-4 explicitly extracted.

关键词： multiloop integrals algebraic algorithms Feynman parameters symbolic calculations dimensional regularization

来源：评论

学校读者我要写书评

暂无评论

algebraic algorithms FOR MATCHING AND MATROID PROBLEMS

引用

SIAM JOURNAL ON COMPUTING 2009年第2期39卷 679-702页

作者： Harvey, Nicholas J. A. MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

We present new algebraic approaches for two well-known combinatorial problems: nonbipartite matching and matroid intersection. Our work yields new randomized algorithms that exceed or match the efficiency of existing algorithms. For nonbipartite matching, we obtain a simple, purely algebraic algorithm with running time O(n(omega)) where n is the number of vertices and omega is the matrix multiplication exponent. This resolves the central open problem of Mucha and Sankowski (2004). For matroid intersection, our algorithm has running time O(nr(omega-1)) for matroids with n elements and rank r that satisfy some natural conditions.

关键词： nonbipartite matching matroid intersection algebraic algorithms fast matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

A Comprehensive Review of Solving Selective Harmonic Elimination Problem With algebraic algorithms

引用

IEEE TRANSACTIONS ON POWER ELECTRONICS 2024年第1期39卷 850-868页

作者： Wang, Chenxu Zhang, Qi Yu, Wensheng Yang, Kehu China Univ Min & Technol Beijing Sch Mech & Elect Engn Beijing 100083 Peoples R China Aalborg Univ AAU Energy DK-9220 Aalborg Denmark Beijing Univ Posts & Telecommun Sch Elect Engn Beijing 100876 Beijing Peoples R China China Univ Min & Technol Beijing Sch Artificial Intelligence Beijing 100083 Peoples R China China Univ Min & Technol Beijing Inner Mongolia Res Inst Minist Emergency Management Peoples Republ China Key Lab Intelligent Min & Robot Ordos 017004 Peoples R China

Selective harmonic elimination pulsewidth modulation (SHEPWM) is an effective way to eliminate low-order harmonics in high-power applications. However, one of the biggest challenges of SHEPWM is to solve the selective harmonic elimination (SHE) equations, which are composed of some nonlinear transcendental equations. Over the past few decades, algebraic algorithms have shown a considerable ability to solve SHE equations, specifically for obtaining all exact solutions. Much research has been published about algebraic algorithms, struggling to solve more switching angles, solving different mathematic models of SHEPWM, and so on. This article comprehensively reviews existing algebraic algorithms, including elementary symmetric polynomials, power sums, Newton's identities, resultant elimination method, Wu's method, Grobner-basis-based method, Chudnovsky algorithm, polynomial homotopy continuation algorithm, and real-time implementation by algebraic algorithms. The principle operation of these methods is summarized, and their performance is analyzed in terms of execution time, solving ability, and applicability for different mathematical models.

关键词： Mathematical models Harmonic analysis Power system harmonics Pulse width modulation Classification algorithms Biological system modeling Voltage algebraic algorithms dc-ac conversion high-power applications inverters renewable energy system selective harmonic elimination (SHE)

来源：评论

学校读者我要写书评

暂无评论

Discriminantal subset convolution: Refining exterior-algebraic methods for parameterized algorithms

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2022年 129卷 62-71页

作者： Brand, Cornelius Vienna Univ Technol Algorithms & Complex Grp Vienna Austria

We give a simplified account of the recent algebraic methods obtained for the longest path problem of Brand, Dell and Husfeldt (STOC'18) and Brand (ESA'19). To this end, we introduce a new kind of subset convolution, discriminantal subset convolution, which we motivate as a distillate of exterior-algebraic operations. The algorithm in the new presentation achieves the almost competitive bound of 2.619k center dot poly(n), first achieved by Fomin et al. (2016) [8], for deterministically finding paths of length k, while it allows for the same running time for the k-internal out-branching problem, improving upon Brand (ESA'19) and reproducing the state-of-the-art of Brand and Pratt (ICALP'21). (c) 2022 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Parameterized algorithms algebraic algorithms Longest path problem Extensor coding Fast subset convolution

来源：评论

学校读者我要写书评

暂无评论

Communication-efficient parallel generic pairwise elimination

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2007年第2期23卷 179-188页

作者： Tiskin, Alexander Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England

The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. In this paper, we consider the parallel complexity of generic pairwise elimination, special cases of which include Gaussian elimination with pairwise pivoting, Gaussian elimination over a finite field, generic Neville elimination and Givens reduction. We develop a new block-recursive, communication-efficient BSP algorithm for generic pairwise elimination. (c) 2006 Elsevier B.V. All rights reserved.

关键词： parallel algorithms algebraic algorithms linear systems

来源：评论

学校读者我要写书评

暂无评论

Trace-Oriented Feature Analysis for Large-Scale Text Data Dimension Reduction

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2011年第7期23卷 1103-1117页

作者： Yan, Jun Liu, Ning Yan, Shuicheng Yang, Qiang Fan, Weiguo (Patrick) Wei, Wei Chen, Zheng Microsoft Res Asia Sigma Ctr Beijing 100190 Peoples R China Natl Univ Singapore Dept Elect & Comp Engn Singapore 117576 Singapore Hong Kong Univ Sci & Technol Dept Comp Sci Kowloon Hong Kong Peoples R China Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Kowloon Hong Kong Peoples R China Virginia Polytech Inst & State Univ Dept Comp Sci Virginia Tech Blacksburg VA 24061 USA Tsinghua Univ Dept Comp Sci Beijing 100871 Peoples R China

Dimension reduction for large-scale text data is attracting much attention nowadays due to the rapid growth of the World Wide Web. We can categorize those popular dimension reduction algorithms into two groups: feature extraction and feature selection algorithms. In the former, new features are combined from their original features through algebraic transformation. Though many of them have been validated to be effective, these algorithms are typically associated with high computational overhead, making them difficult to be applied on real-world text data. In the latter, subsets of features are selected directly. These algorithms are widely used in real-world tasks owing to their efficiency, but are often based on greedy strategies rather than optimal solutions. An important problem remains: it has been troublesome to integrate these two types of algorithms into a single framework, making it difficult to reap the benefits from both. In this paper, we formulate the two algorithm categories through a unified optimization framework, under which we develop a novel feature selection algorithm called Trace-Oriented Feature Analysis (TOFA). In detail, we integrate the objective functions of several state-of-the-art feature extraction algorithms into a unified one under the optimization framework, and then we propose to optimize this objective function in the solution space of feature selection algorithms for dimensionality reduction. Since the proposed objective function of TOFA integrates many prominent feature extraction algorithms' objective functions, such as unsupervised Principal Component Analysis (PCA) and supervised Maximum Margin Criterion (MMC), TOFA can handle both supervised and unsupervised problems. In addition, by tuning a weight value, TOFA is also suitable to solve semisupervised learning problems. Experimental results on several real-world data sets validate the effectiveness and efficiency of TOFA in text data for dimensionality reduction purpose.

关键词： algebraic algorithms computations on matrices document analysis global optimization

来源：评论

学校读者我要写书评

暂无评论

algorithms FOR WEIGHTED MATCHING GENERALIZATIONS II: f-FACTORS AND THE SPECIAL CASE OF SHORTEST PATHS

引用

SIAM JOURNAL ON COMPUTING 2021年第2期50卷 555-601页

作者： Gabow, Harold N. Sankowski, Piotr Univ Colorado Dept Comp Sci Boulder CO 80309 USA Univ Warsaw Inst Informat Banacha 2 PL-02097 Warsaw Poland Sapienza Univ Rome Dept Comp & Syst Sci I-00185 Rome Italy

For an undirected graph or multigraph G = (V;E) and a function f : V -> Z(+), an f-factor is a subgraph whose degree function is f. For integral edge weights of maximum magnitude W our algorithm finds a maximum weight f -factor in time O (Wf(V)!), where f (V) = P v2V f (v) and ! is the exponent of matrix multiplication. The algorithm is randomized and has two versions. For worst-case time the algorithm is correct with high probability. For expected time the algorithm is Las Vegas. The algorithm is based on a detailed analysis of the structure of the optimum blossoms. A special case gives a representation for single-source shortest-paths in conservative undirected graphs, generalizing the standard shortest-path tree to a "tree of cycles". The representation can be constructed by a randomized algorithm with the same time bound as above, or deterministically by an algorithm for maximum weight matching, achieving time O(n(m +n log n)) or O (p n m log (nW)).

关键词： algebraic algorithms matchings factors shortest paths

来源：评论

学校读者我要写书评

暂无评论

Building Above Read-Once Polynomials: Identity Testing and Hardness of Representation

引用

ALGORITHMICA 2016年第4期76卷 890-909页

作者： Mahajan, Meena Rao, B. V. Raghavendra Sreenivasaiah, Karteek Inst Math Sci Madras Tamil Nadu India Indian Inst Technol Madras Tamil Nadu India Max Planck Inst Informat Saarbrucken Germany

Polynomial Identity Testing (PIT) algorithms have focussed on polynomials computed either by small alternation-depth arithmetic circuits, or by read-restricted formulas. Read-once polynomials (ROPs) are computed by read-once formulas (ROFs) and are the simplest of read-restricted polynomials. Building structures above these, we show the following: (1) a deterministic polynomial-time non-black-box PIT algorithm for . (2) Weak hardness of representation theorems for sums of powers of constant-free ROPs and for s of the form . (3) A partial characterization of multilinear monotone constant-free ROPs.

关键词： Polynomial Identity Testing algebraic algorithms Arithmetic circuits

来源：评论

学校读者我要写书评

暂无评论

Computing elementary symmetric polynomials with a subpolynomial number of multiplications

引用

SIAM JOURNAL ON COMPUTING 2003年第6期32卷 1475-1487页

作者： Grolmusz, V Eotvos Lorand Univ Dept Comp Sci H-1117 Budapest Hungary

Elementary symmetric polynomials S-n(k) are the building blocks of symmetric polynomials. In this work we prove that for constant k's, S-n(k) modulo composite numbers m = p(1)p(2) can be computed using only n(o(1)) multiplications if the coefficients of monomials x(i1) x(i2) ... x(ik) are allowed to be 1 either mod p(1) or mod p(2) but not necessarily both. To the best of our knowledge, no previous result yielded even a sublinear (i.e., n(epsilon), 0 < epsilon < 1) number of multiplications for similar tasks. Moreover, our algorithm fits in the model of the most restrictive depth-3 arithmetic circuits ( homogeneous, multilinear, or the graph model). In contrast, by a lower bound of Nisan and Wigderson [Comput. Complexity, 6 (1997), pp. 217 - 234], any homogeneous depth-3 circuit needs size Omega((n/2k)(k/2)) for computing S-n(k) modulo primes. Moreover, the number of multiplications in our algorithm remains sublinear while k = O(log log n). Our results generalize for other nonprime-power composite moduli as well. The proof uses perfect hashing functions and the famous BBR polynomial of Barrington, Beigel, and Rudich.

关键词： symmetric polynomials arithmetic circuits algebraic algorithms composite modulus

来源：评论

学校读者我要写书评

暂无评论

Fast Dynamic Transitive Closure with Lookahead

引用

ALGORITHMICA 2010年第2期56卷 180-197页

作者： Sankowski, Piotr Mucha, Marcin Warsaw Univ Inst Informat PL-02097 Warsaw Poland

In this paper we consider the problem of dynamic transitive closure with lookahead. We present a randomized one-sided error algorithm with updates and queries in O(n(omega(1,1,epsilon)-epsilon)) time given a lookahead of n(epsilon) operations, where omega(1,1,epsilon) is the exponent of multiplication of n x n matrix by n x n(epsilon) matrix. For epsilon <= 0.294 we obtain an algorithm with queries and updates in O(n(2-epsilon)) time, whereas for epsilon = 1 the time is O(n(omega-1)). This is essentially optimal as it implies an O(n(omega)) algorithm for boolean matrix multiplication. We also consider the offline transitive closure in planar graphs. For this problem, we show an algorithm that requires O(n(omega/2)) time to process n(1/2) operations. We also show a modification of these algorithms that gives faster amortized queries. Finally, we give faster algorithms for restricted type of updates, so called element updates. All of the presented algorithms are randomized with one-sided error. All our algorithms are based on dynamic algorithms with lookahead for matrix inverse, which are of independent interest.

关键词： Transitive closure Dynamic algorithms Lookahead algebraic algorithms Matrix inverse Planar graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：