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

A new fast root-finder for black box polynomials

THEORETICAL COMPUTER SCIENCE 2025年 1027卷

作者： Pan, Victor Y. Go, Soo Luan, Qi Zhao, Liang City Univ New York Lehman Coll Dept Comp Sci Bronx NY 10468 USA City Univ New York Grad Ctr PhD Program Math New York NY 10036 USA City Univ New York Grad Ctr PhD Program Comp Sci New York NY 10036 USA

Univariate polynomial root-finding has been studied for four millennia and very intensively in the last decades. Our black box root-finder involves no coefficients and works for a black box polynomial, defined by an oracle (that is, black box subroutine) for its evaluation. Such root-finders have various benefits, e.g., are particularly efficient where a polynomial can be evaluated fast, say, is the sum of a small number of shifted monomials (x - c)(a). With incorporation of a fast algorithm by the first author for compression of a disc on the complex plane without losing roots, our root-finder approximates all d complex zeros of a dth degree polynomial p(x) (aka roots of equation p(x) = 0) by using near-optimal Las Vegas expected number of bit-operations,(1) that is, the root-finder is expected to run almost as fast as one accesses the coefficients with a precision required for the solution within a prescribed error bound. The only other known near-optimal polynomial root-finder was presented by the first author at ACM STOC 1995. It is quite involved and has never been implemented, while already in its initial implementation our new root-finder competed with user's choice package of root-finding subroutines MPSolve, according to extensive numerical experiments with standard test polynomials. Furthermore we readily extend our black box root-finder to approximation of the eigenvalues of a matrix in record expected bit operation time, while the root-finder of STOC 1995, using the coefficients of p(x), does not support such extension.

关键词： Polynomial computations symbolic-numeric computing Polynomial zeros Complexity Black box polynomials Matrix eigenvalues

来源：评论

学校读者我要写书评

暂无评论

symbolic-numeric algorithm for parameter estimation in discrete-time models with exp

引用

JOURNAL OF symbolic COMPUTATION 2025年 128卷

作者： Berman, Yosef Forrest, Joshua Grote, Matthew Ovchinnikov, Alexey Rueda, Sonia L. CUNY Grad Ctr PhD Program Math New York NY 10016 USA CUNY Grad Ctr PhD Program Comp Sci New York NY USA CUNY Queens Coll Dept Math Queens NY USA Univ Politecn Madrid Dept Matemat Aplicada ETS Arquitectura Madrid Spain Univ Melbourne Sch Math & Stat Parkville Vic Australia

Dynamic models describe phenomena across scientific disciplines, yet to make these models useful in application the unknown parameter values of the models must be determined. Discrete-time dynamic models are widely used to model biological processes, but it is often difficult to determine these parameters. In this paper, we propose a symbolic-numeric approach for parameter estimation in discrete-time models that involve univariate nonalgebraic (locally) analytic functions such as exp. We illustrate the performance (precision) of our approach by applying our approach to two archetypal discrete-time models in biology (the flour beetle 'LPA' model and discrete Lotka-Volterra competition model). Unlike optimization-based methods, our algorithm guarantees to find all solutions of the parameter values up to a specified precision given time-series data for the measured variables provided that there are finitely many parameter values that fit the data and that the used polynomial system solver can find all roots of the associated polynomial system with interval coefficients. (c) 2024 Elsevier Ltd. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： Parameter estimation Discrete-time models symbolic-numeric computing Flour beetle model

来源：评论

学校读者我要写书评

暂无评论

Nearly Optimal Black Box Polynomial Root-finders 35

Nearly Optimal Black Box Polynomial Root-finders

引用

35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

作者： Pan, Victor Y. CUNY Herbert H Lehman Coll Dept Comp Sci Bronx NY 10468 USA CUNY Grad Sch & Univ Ctr Program Math New York NY 10036 USA CUNY Grad Sch & Univ Ctr Program Comp Sci New York NY 10036 USA

ISBN: (纸本)9781611977912

Univariate polynomial root-finding has been studied for four millennia and very intensively in the last decades. Our novel nearly optimal Las Vegas randomized root-finders approximate all zeros of a polynomial almost as fast as one accesses its coefficients with the precision required for the solution within a prescribed error bound.(1) Moreover, our root-finders can be applied to a black box polynomial, defined by an oracle (that is, black box subroutine) for its evaluation rather than by its coefficients. Such root-finders are particularly fast for polynomials that can be evaluated fast, e.g., the sum of a few shifted monomials, but the only other known black box root-finder is the pioneering one by Louis and Vempala at FOCS 2016, and it only approximates the absolutely largest root of a real-rooted polynomial. Our deterministic divide and conquer algorithm of ACM STOC 1995 is the only other known nearly optimal polynomial root-finder, and it extensively uses the coefficients, is quite involved, and has never been implemented, while according to extensive numerical experiments with standard test polynomials, already initial implementations of our new root-finders compete with user's choice package of root-finding subroutine MPSolve and supersede it more and more significantly where the degree of a polynomial grows large. Our root-finders are readily extended to support approximation of the eigenvalues of a matrix within a record Las Vegas expected bit operation time bound. Our auxiliary algorithms and techniques for computations with black box polynomials can be of independent interest.

关键词： polynomial computations matrix eigenvalues complexity polynomial zeros black box polynomials root-squaring symbolic-numeric computing

来源：评论

学校读者我要写书评

暂无评论

Root-Squaring for Root-Finding 1

引用

25th International Workshop on Computer Algebra in Scientific computing (CASC)

作者： Go, Soo Pan, Victor Y. Soto, Pedro CUNY Dept Comp Sci Lehman Coll Bronx NY 10468 USA CUNY PhD Programs Math & Comp Sci Grad Ctr New York NY 10016 USA Univ Oxford Math Inst Oxford England

ISBN: (数字)9783031417245

ISBN: (纸本)9783031417238;9783031417245

The root-squaring iterations of Dandelin (1826), Lobachevsky (1834), and Graffe (1837) recursively produce the coefficients of polynomials ph(x) whose zeros are the 2(h)th powers of the zeros of an input polynomial p(x) for h = 1, 2, 3,... The iterations have been the main tool for univariate polynomial root-finding in the 19th century and well beyond but became obsolete later because of severe numerical stability problems observed already in a few iterations. To circumvent this deficiency we apply root-squaring to Newton's Inverse Ratios p'(x)/p(x) and compute no coefficients of p(x) or ph(x) for h > 0, assuming that p(x) is a black box polynomial, represented by an oracle or subroutine for its evaluation rather than by its coefficients. Accordingly, our algorithm accelerates root-squaring for a polynomial p(x) that can be evaluated fast as well as for polynomial t(c,rho)(x) = p(x-c/rho) for a complex number c and a positive rho by performing root-squaring without computing the coefficients of t(c,rho)(x). Our extensive experiments demonstrate efficiency of application of our algorithms to estimation of extremal root radii, that is, the maximal and minimal distances from a point on the complex plane to the zeros of p(x). This is a well-known ingredient of various efficient polynomial root-finders, immediately extended to deciding whether a fixed disc on the complex plane contains any zero of p(x). The latter decision, called exclusion test for a disc, is the basic step of all efficient root-finders using subdivision iterations, in particular, of the recent polynomial root-finder by the second author, made nearly optimal due to a distinct application of root-squaring iterations.

关键词： symbolic-numeric computing Root-finding Polynomial algorithms Computer algebra

来源：评论

学校读者我要写书评

暂无评论

computing nearby non-trivial Smith forms

引用

JOURNAL OF symbolic COMPUTATION 2021年 102卷 304-327页

作者： Giesbrecht, Mark Haraldson, Joseph Labahn, George Univ Waterloo Cheriton Sch Comp Sci Waterloo ON Canada

We consider the problem of computing the nearest matrix polynomial with a non-trivial Smith Normal Form. We show that computing the Smith form of a matrix polynomial is amenable to numeric computation as an optimization problem. Furthermore, we describe an effective optimization technique to find a nearby matrix polynomial with a non-trivial Smith form. The results are then generalized to include the computation of a matrix polynomial having a maximum specified number of ones in the Smith Form (i.e., with a maximum specified McCoy rank). We discuss the geometry and existence of solutions and how our results can be used for an error analysis. We develop an optimization-based approach and demonstrate an iterative numerical method for computing a nearby matrix polynomial with the desired spectral properties. We also describe an implementation of our algorithms and demonstrate the robustness with examples in Maple. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Matrix polynomials Smith normal form symbolic-numeric computing

来源：评论

学校读者我要写书评

暂无评论

Multi-graded Macaulay dual spaces

引用

JOURNAL OF ALGEBRA AND ITS APPLICATIONS 2024年第0期

作者： Cummings, Joseph Hauenstein, Jonathan D. Univ Notre Dame Appl & Computat Math & Stat Notre Dame IN 46556 USA

We describe an algorithm for computing Macaulay dual spaces for multi-graded ideals. For homogeneous ideals, the natural grading is inherited by the Macaulay dual space which has been leveraged to develop algorithms to compute the Macaulay dual space in each homogeneous degree. Our main theoretical result extends this idea to multi-graded Macaulay dual spaces inherited from multi-graded ideals. This natural duality allows ideal operations to be translated from homogeneous ideals to their corresponding operations on the multi-graded Macaulay dual spaces. In particular, we describe a linear operator with a right inverse for computing quotients by a multi-graded polynomial. By using a total ordering on the homogeneous components of the Macaulay dual space, we also describe how to recursively construct a basis for each component. Several examples are included to demonstrate this new approach.

关键词： Macaulay dual spaces Hilbert functions multi-grading symbolic-numeric computing

来源：评论

学校读者我要写书评

暂无评论

computing lower rank approximations of matrix polynomials

引用

JOURNAL OF symbolic COMPUTATION 2020年 98卷 225-245页

作者： Giesbrecht, Mark Haraldson, Joseph Labahn, George Univ Waterloo Cheriton Sch Comp Sci Waterloo ON Canada

Given an input matrix polynomial whose coefficients are floating point numbers, we consider the problem of finding the nearest matrix polynomial which has rank at most a specified value. This generalizes the problem of finding a nearest matrix polynomial that is algebraically singular with a prescribed lower bound on the dimension given in a previous paper by the authors. In this paper we prove that such lower rank matrices at minimal distance always exist, satisfy regularity conditions, and are all isolated and surrounded by a basin of attraction of non-minimal solutions. In addition, we present an iterative algorithm which, on given input sufficiently close to a rank-at-most matrix, produces that matrix. The algorithm is efficient and is proven to converge quadratically given a sufficiently good starting point. An implementation demonstrates the effectiveness and numerical robustness of our algorithm in practice. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Matrix polynomials symbolic-numeric computing Low-rank approximation

来源：评论

学校读者我要写书评

暂无评论

Matrix Multiplication Over Word-Size Modular Rings Using Approximate Formulas

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2016年第3期42卷 20-20页

作者： Boyer, Brice Dumas, Jean-Guillaume NCSU Dept Math Raleigh NC 27695 USA Univ Grenoble Alpes Grenoble France CNRS Umr 5224 Lab J Kuntzmann 51Rue MathBp 53X F-38041 Grenoble France

Bini-Capovani-Lotti-Romani approximate formula (or border rank) for matrix multiplication achieves a better complexity than Strassen's matrix multiplication formula. In this article, we show a novel way to use the approximate formula in the special case where the ring is Z/pZ. In addition, we show an implementation a la FFLAS-FFPACK, where p is a word-size modulo, that improves on state-of-the-art Z/pZ matrix multiplication implementations.

关键词： Algorithms Performance Exact linear algebra matrix multiplication efficient implementations Strassen-Winograd's algorithm Bini-Capovani-Lotti-Romani approximate bilinear algorithm symbolic-numeric computing memory placement and scheduling

来源：评论

学校读者我要写书评

暂无评论

symbolic-numeric sparse interpolation of multivariate polynomials

引用

JOURNAL OF symbolic COMPUTATION 2009年第8期44卷 943-959页

作者： Giesbrecht, Mark Labahn, George Lee, Wen-shin Univ Waterloo David R Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada Univ Antwerp Dept Wiskunde Informat Antwerp Belgium

We consider the problem of sparse interpolation of an approximate multivariate black-box polynomial in floating point arithmetic. That is, both the inputs and outputs of the black-box polynomial have some error, and all numbers are represented in standard, fixed-precision, floating point arithmetic. By interpolating the black box evaluated at random primitive roots of unity, we give efficient and numerically robust Solutions. We note the similarity between the exact Ben-Or/Tiwari sparse interpolation algorithm and the classical Prony's method for interpolating a sum of exponential functions, and exploit the generalized eigenvalue reformulation of Prony's method. We analyse the numerical stability of our algorithms and the sensitivity of the Solutions, as well as the expected conditioning achieved through randomization. Finally, we demonstrate the effectiveness of our techniques in practice through numerical experiments and applications. (C) 2008 Elsevier Ltd. All rights reserved.

关键词： symbolic-numeric computing Multivariate interpolation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：