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

On the complexity of computing determinants

COMPUTATIONAL COMPLEXITY 2005年第3-4期13卷 91-130页

作者： Kaltofen, E Villard, G N Carolina State Univ Dept Math Raleigh NC 27695 USA Ecole Normale Super Lyon Lab LIP F-69364 Lyon 07 France

We present new baby steps/giant steps algorithms of asymptotically fast running time for dense matrix problems. Our algorithms compute the determinant, characteristic polynomial, Frobenius normal form and Smith normal form of a dense n x n matrix A with integer entries in ( n(3.2) log \\A\\s)(1+o( 1)) and ( n(2.697263) log \\A\\) (1+o( 1)) bit operations;here \\A\\ denotes the largest entry in absolute value and the exponent adjustment by "+o(1)" captures additional factors C-1( log n) (C2)( loglog \\A\\)(C3) for positive real constants C1, C2, C3. The bit complexity ( n(3.2) log \\A\\)(1+o( 1)) results from using the classical cubic matrix multiplication algorithm. Our algorithms are randomized, and we can certify that the output is the determinant of A in a Las Vegas fashion. The second category of problems deals with the setting where the matrix A has elements from an abstract commutative ring, that is, when no divisions in the domain of entries are possible. We present algorithms that deterministically compute the determinant, characteristic polynomial and adjoint of A with n(3.2+o( 1)) and O(n(2.697263)) ring additions, subtractions and multiplications.

关键词： integer matrix matrix determinant characteristic polynomial Smith normal form bit complexity division-free complexity randomized algorithm multivariable control theory realization matrix sequence block Wiedemann algorithm block Lanczos algorithm

来源：评论

学校读者我要写书评

暂无评论

Multidimensional butterfly factorization

引用

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS 2018年第3期44卷 737-758页

作者： Li, Yingzhou Yang, Haizhao Ying, Lexing Stanford Univ Dept Math Stanford CA 94305 USA Stanford Univ ICME Stanford CA 94305 USA Duke Univ Dept Math Durham NC 27706 USA

This paper introduces the multidimensional butterfly factorization as a data-sparse representation of multidimensional kernel matrices that satisfy the complementary low-rank property. This factorization approximates such a kernel matrix of size N x N with a product of O(log N) sparse matrices, each of which contains O(N) nonzero entries. We also propose efficient algorithms for constructing this factorization when either (i) a fast algorithm for applying the kernel matrix and its adjoint is available or (ii) every entry of the kernel matrix can be evaluated in O(1) operations. For the kernel matrices of multidimensional Fourier integral operators, for which the complementary low-rank property is not satisfied due to a singularity at the origin, we extend this factorization by combining it with either a polar coordinate transformation or a multiscale decomposition of the integration domain to overcome the singularity. Numerical results are provided to demonstrate the efficiency of the proposed algorithms. (c) 2017 Elsevier Inc. All rights reserved.

关键词： Data-sparse matrix factorization Operator compression Butterfly algorithm randomized algorithm Fourier integral operators

来源：评论

学校读者我要写书评

暂无评论

INITIAL-BOUNDARY VALUE PROBLEM FOR THE HEAT EQUATION-A STOCHASTIC algorithm

引用

ANNALS OF APPLIED PROBABILITY 2018年第3期28卷 1943-1976页

作者： Deaconu, Madalina Herrmann, Samuel INRIA F-54600 Villers Les Nancy France Univ Lorraine Inst Elie Cartan Lorraine UMR 7502 CNRS F-54506 Vandoeuvre Les Nancy France Univ Bourgogne Franche Comte UMR 5584 IMB CNRS F-21000 Dijon France

The initial-boundary value problem for the heat equation is solved by using an algorithm based on a random walk on heat balls. Even if it represents a sophisticated generalization of the Walk on Spheres (WOS) algorithm introduced to solve the Dirichlet problem for Laplace's equation, its implementation is rather easy. The construction of this algorithm can be considered as a natural consequence of previous works the authors completed on the hitting time approximation for Bessel processes and Brownian motion [Ann. Appl. Probab. 23 (2013) 2259-2289, Math. Comput. Simulation 135 (2017) 28-38, Bernoulli 23 (2017) 3744-3771]. A similar procedure was introduced previously in the paper [Random Processes for Classical Equations of Mathematical Physics (1989) Kluwer Academic]. The definition of the random walk is based on a particular mean value formula for the heat equation. We present here a probabilistic view of this formula. The aim of the paper is to prove convergence results for this algorithm and to illustrate them by numerical examples. These examples permit to emphasize the efficiency and accuracy of the algorithm.

关键词： Initial-boundary value problem heat equation random walk mean-value formula heat balls Riesz potential submartingale randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2006年第11期5卷 1620-1632页

作者： Luo, Hong Liu, Yonghe Das, Sajal K. Beijing Univ Posts & Telecommun Coll Comp Sci & Technol Beijing 100876 Peoples R China Univ Texas Dept Comp Sci & Engn Arlington TX 76019 USA

In this paper, we propose a routing algorithm called Minimum Fusion Steiner Tree (MFST) for energy efficient data gathering with aggregation ( fusion) in wireless sensor networks. Different from existing schemes, MFST not only optimizes over the data transmission cost, but also incorporates the cost for data fusion, which can be significant for emerging sensor networks with vectorial data and/or security requirements. By employing a randomized algorithm that allows fusion points to be chosen according to the nodes' data amounts, MFST achieves an approximation ratio of 5/4 log(k+1), where k denotes the number of source nodes, to the optimal solution for extremely general system setups, provided that fusion cost and data aggregation are nondecreasing against the total input data. Consequently, in contrast to algorithms that only excel in full or nonaggregation scenarios without considering fusion cost, MFST can thrive in a wide range of applications.

关键词： wireless sensor networks data fusion routing randomized algorithm approximation

来源：评论

学校读者我要写书评

暂无评论

Certified dense linear system solving

引用

JOURNAL OF SYMBOLIC COMPUTATION 2004年第4期37卷 485-510页

作者： Mulders, T Storjohann, A Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada COMIT AG CH-8004 Zurich Switzerland

A randomized algorithm is given for solving a system of linear equations over a principal ideal domain. The algorithm returns a solution vector which has minimal denominator. A certificate of minimality is also computed. A given system has a Diophantine solution precisely when the minimal denominator is one. Cost estimates are given for systems over the ring of integers and ring of polynomials with coefficients from a field. (C) 2003 Elsevier Ltd. All rights reserved.

关键词： linear system solution diophantine system solution integer matrix polynomial matrix randomized algorithm Las Vegas

来源：评论

学校读者我要写书评

暂无评论

Early termination in sparse interpolation algorithms

引用

JOURNAL OF SYMBOLIC COMPUTATION 2003年第3-4期36卷 365-400页

作者： Kaltofen, E Lee, ES N Carolina State Univ Dept Math Raleigh NC 27695 USA Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada

A probabilistic strategy, early termination, enables different interpolation algorithms to adapt to the degree or the number of terms in the target polynomial when neither is supplied in the input. In addition to dense algorithms, we implement this strategy in sparse interpolation algorithms. Based on early termination, racing algorithms execute simultaneously dense and sparse algorithms. The racing algorithms can be embedded as the univariate interpolation substep within Zippel's multivariate method. In addition, we experimentally verify some heuristics of early termination, which make use of thresholds and post-verification. (C) 2003 Elsevier Ltd. All rights reserved.

关键词： early termination sparse polynomial black box polynomial interpolation sparse interpolation randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Randomization helps to perform independent tasks reliably

引用

RANDOM STRUCTURES & algorithmS 2004年第1期24卷 11-41页

作者： Chlebus, BS Kowalski, DR Univ Colorado Dept Comp Sci & Engn Denver CO 80217 USA Warsaw Univ Inst Informat PL-02097 Warsaw Poland

This paper is about algorithms that schedule tasks to be performed in a distributed failure-prone environment, when processors communicate by message-passing, and when tasks are independent and of unit length. The processors work under synchrony and may fail by crashing. Failure patterns are imposed by adversaries. Linearly-bounded adversaries may fail up to a constant fraction of the processors. Weakly-adaptive adversaries have to select, prior to the start of an execution, a subset of processors to be failure-prone, and then may fail only the selected processors, at arbitrary steps, in the course of the execution. Strongly adaptive adversaries have a total number of failures as the only restriction on failure patterns. The measures of complexity are work, measured as the available processor steps, and communication, measured as the number of point-to-point messages. A randomized algorithm is developed, that attains both O(n log*n) expected work and O(n log*n) expected communication, against weakly-adaptive linearly-bounded adversaries, in the case when the numbers of tasks and processors are both equal to n. This is in contrast with performance of algorithms against strongly-adaptive linearly-bounded adversaries, which has to be Omega(n log n/log log n) in terms of work. (C) 2003 Wiley Periodicals, Inc.

关键词： distributed algorithm randomized algorithm message passing crash failures adaptive adversary independent tasks load balancing lower bound

来源：评论

学校读者我要写书评

暂无评论

ON THE COMPLEXITY OF INVERTING INTEGER AND POLYNOMIAL MATRICES

引用

COMPUTATIONAL COMPLEXITY 2015年第4期24卷 777-821页

作者： Storjohann, Arne Univ Waterloo David R Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada

An algorithm is presented that probabilistically computes the exact inverse of a nonsingular n x n integer matrix A using (n(3)(log parallel to A parallel to + log kappa(A)))(1+o(1)) bit operations. Here, parallel to A parallel to = max(ij) |A(ij)| denotes the largest entry in absolute value, kappa(A) := n parallel to A(-1)parallel to parallel to A parallel to is the condition number of the input matrix, and the "+ o(1)" in the exponent indicates a missing factor c(1)(log n)(c2)(loglog parallel to A parallel to)(c3) for positive real constants c(1), c(2), c(3). A variation of the algorithm is presented for polynomial matrices that computes the inverse of a nonsingular nxn matrix whose entries are polynomials of degree d over a field using (n(3)d)(1+o(1)) field operations. Both algorithms are randomized of the Las Vegas type: failure may be reported with probability at most 1/2, and if failure is not reported, then the output is certified to be correct in the same running time bound.

关键词： Integer matrix polynomial matrix matrix inverse Smith normal form bit complexity randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Opinion Dynamics With Topological Gossiping: Asynchronous Updates Under Limited Attention

引用

IEEE CONTROL SYSTEMS LETTERS 2020年第3期4卷 566-571页

作者： Rossi, Wilbert Samuel Frasca, Paolo Univ Twente Dept Appl Math NL-7500 AE Enschede Netherlands Univ Groningen Univ Coll Groningen NL-9701 BA Groningen Netherlands Univ Grenoble Alpes Inria CNRS Grenoble INPGIPSA Lab F-38000 Grenoble France

This letter introduces a general model of opinion dynamics with opinion-dependent connectivity. Agents update their opinions asynchronously: for the updating agent, the new opinion is the average of the k closest opinions within a subset of m agents that are sampled from the population of size n. Depending on k and m with respect to n, the dynamics can have a variety of equilibria, which include consensus and clustered configurations. The model covers as special cases a classical gossip update (if m = n) and a deterministic update defined by the k nearest neighbors (if m = k). We prove that the dynamics converges to consensus if n > 2(m - k). Before convergence, however, the dynamics can remain for long time in the vicinity of metastable clustered configurations.

关键词： Convergence Sociology Mathematical model Nickel Statistics Indexes Social network services Agent-based systems large-scale systems network analysis and control randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Wireless random-access networks with bipartite interference graphs

引用

RANDOM STRUCTURES & algorithmS 2024年第4期64卷 814-855页

作者： Borst, Sem C. den Hollander, Frank Nardi, Francesca R. Sfragara, Matteo Eindhoven Univ Technol Dept Math & Comp Sci Eindhoven Netherlands Leiden Univ Math Inst Leiden Netherlands Univ Florence Dept Math Florence Italy Stockholm Univ Dept Math Stockholm Sweden

We consider random-access networks where nodes represent servers with a queue and can be either active or inactive. A node deactivates at unit rate, while it activates at a rate that depends on its queue length, provided none of its neighbors is active. We consider arbitrary bipartite graphs in the limit as the initial queue lengths become large and identify the transition time between the two states where one half of the network is active and the other half is inactive. The transition path is decomposed into a succession of transitions on complete bipartite subgraphs. We formulate a randomized greedy algorithm that takes the graph as input and gives as output the set of transition paths the network is most likely to follow. Along each path we determine the mean transition time and its law on the scale of its mean. Depending on the activation rates, we identify three regimes of behavior.

关键词： activation protocols bipartite interference graphs random-access networks randomized algorithm transition time

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：