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

Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study

JOURNAL OF COMPLEXITY 2005年第4期21卷 502-531页

作者： De Leo, M Dratman, E Matera, G Univ Nacl Gen Sarmiento Inst Desarrollo Humano RA-1613 Los Polvorines BA Argentina Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Matemat RA-1428 Buenos Aires DF Argentina Consejo Nacl Invest Cient & Tecn Consejo Nacl Invest Cient & Tecnol RA-1033 Buenos Aires DF Argentina

We consider a family of polynomial systems which arises in the analysis of the stationary solutions of a standard discretization of certain semi-linear second-order parabolic partial differential equations. We prove that this family is well-conditioned from the numeric point of view, and ill-conditioned from the symbolic point of view. We exhibit a polynomial-time numeric algorithm solving any member of this family, which significantly contrasts the exponential behavior of all known symbolic algorithms solving a generic instance of this family of systems. (c) 2005 Elsevier Inc. All rights reserved.

关键词： polynomial system solving homotopy algorithms conditioning complexity semi-linear parabolic problems stationary solutions

来源：评论

学校读者我要写书评

暂无评论

Stability verification for monotone systems using homotopy algorithms

引用

NUMERICAL algorithms 2011年第4期58卷 529-543页

作者： Rueffer, Bjoern S. Wirth, Fabian R. Univ Paderborn Inst Elektrotech & Informat Tech D-33098 Paderborn Germany Univ Wurzburg Inst Math D-97074 Wurzburg Germany

A monotone self-mapping of the nonnegative orthant induces a monotone discrete-time dynamical system which evolves on the same orthant. If with respect to this system the origin is attractive then there must exist points whose image under the monotone map is strictly smaller than the original point, in the component-wise partial ordering. Here it is shown how such points can be found numerically, leading to a recipe to compute order intervals that are contained in the region of attraction and where the monotone map acts essentially as a contraction. An important application is the numerical verification of so-called generalized small-gain conditions that appear in the stability theory of large-scale systems.

关键词： Monotone systems Stability theory homotopy algorithms

来源：评论

学校读者我要写书评

暂无评论

Probability-one homotopy algorithms for robust controller synthesis with fixed-structure multipliers

引用

INTERNATIONAL JOURNAL OF ROBUST AND NONLINEAR CONTROL 1997年第2期7卷 165-185页

作者： Collins, EG Haddad, WM Watson, LT Sadhukhan, D GEORGIA INST TECHNOL SCH AEROSP ENGN ATLANTA GA 30332 USA VIRGINIA POLYTECH INST & STATE UNIV DEPT COMP SCI BLACKSBURG VA 24061 USA VIRGINIA POLYTECH INST & STATE UNIV DEPT MATH BLACKSBURG VA 24061 USA

Continuation algorithms that avoid multiplier-controller iteration have been developed earlier for fixed-architecture, mixed structured singular value controller synthesis. These algorithms have only been formulated for the special case of Popov multipliers and rely on an ad hoc initialization scheme. In addition, the algorithms have not used the prediction capabilities obtained by computing the Jacobian matrix of the continuation (or homotopy) map, and have assumed that the homotopy zero curve is monotonic. This paper develops probability-one homotopy algorithms based on the use of general fixed-structure multipliers. These algorithms can be initialized using an arbitrary (admissible) multiplier and a stabilizing compensator. In addition, as with all probability-one algorithms, the homotopy zero curve is not assumed to be monotonic and prediction is accomplished by using the homotopy Jacobian matrix. This approach also appears to have some advantages over the bilinear matrix inequality (BMI) approaches resulting from extensions of the LMI framework for robustness analysis.

关键词： fixed-structure multipliers multivariable stability margin LMI's BMI's homotopy algorithms

来源：评论

学校读者我要写书评

暂无评论

PROBABILITY-ONE homotopy algorithms FOR ROBUST CONTROLLER SYNTHESIS WITH FIXED-STRUCTURE MULTIPLIERS

引用

International Journal of Robust and Nonlinear Control 1998年第2期7卷

作者： Emmanuel G. Collins Jr. Wassim M. Haddad Layne T. Watson Debashis Sadhukhan Department of Mechanical Engineering Florida A&M—Florida State 2525 Pottsdamer Street Tallahassee FL 32310-6046 U.S.A. School of Aerospace Engineering Georgia Institute of Technology Atlanta GA 30332-0150 U.S.A. Departments of Computer Science and Mathematics Virginia Polytechnic Institute and State University Blacksburg VA 24061-0106 U.S.A.

Continuation algorithms that avoid multiplier–controller iteration have been developed earlier for fixed-architecture, mixed structured singular value controller synthesis. These algorithms have only been formulated for the special case of Popov multipliers and rely on an ad hoc initialization scheme. In addition, the algorithms have not used the prediction capabilities obtained by computing the Jacobian matrix of the continuation (or homotopy) map, and have assumed that the homotopy zero curve is monotonic. This paper develops probability-one homotopy algorithms based on the use of general fixed-structure multipliers. These algorithms can be initialized using an arbitrary (admissible) multiplier and a stabilizing compensator. In addition, as with all probability-one algorithms, the homotopy zero curve is not assumed to be monotonic and prediction is accomplished by using the homotopy Jacobian matrix. This approach also appears to have some advantages over the bilinear matrix inequality (BMI) approaches resulting from extensions of the LMI framework for robustness analysis. © 1997 by John Wiley & Sons, Ltd.

关键词： fixed-structure multipliers multivariable stability margin LMI's BMI's homotopy algorithms

来源：评论

学校读者我要写书评

暂无评论

Online graph topology learning from matrix-valued time series

引用

COMPUTATIONAL STATISTICS & DATA ANALYSIS 2025年 202卷

作者： Jiang, Yiye Bigot, Jeremie Maabout, Sofian Univ Grenoble Alpes CNRS Inria Grenoble INPLJK F-38000 Grenoble France Univ Bordeaux Inst Math Bordeaux F-33405 Talence France Univ Bordeaux Lab Bordelais Rech Informat F-33405 Talence France

The focus is on the statistical analysis of matrix-valued time series, where data is collected over a network of sensors, typically at spatial locations, over time. Each sensor records a vector of features at each time point, creating a vectorial time series for each sensor. The goal is to identify the dependency structure among these sensors and represent it with a graph. When only one feature per sensor is observed, vector auto-regressive (VAR) models are commonly used to infer Granger causality, resulting in a causal graph. The first contribution extends VAR models to matrix-variate models for the purpose of graph learning. Additionally, two online procedures are proposed for both low and high dimensions, enabling rapid updates of coefficient estimates as new samples arrive. In the high-dimensional setting, a novel Lasso-type approach is introduced, and homotopy algorithms are developed for online learning. An adaptive tuning procedure for the regularization parameter is also provided. Given that the application of auto-regressive models to data typically requires detrending, which is not feasible in an online context, the proposed AR models are augmented by incorporating trend as an additional parameter, with a particular focus on periodic trends. The online algorithms are adapted to these augmented data models, allowing for simultaneous learning of the graph and trend from streaming samples. Numerical experiments using both synthetic and real data demonstrate the effectiveness of the proposed methods.

关键词： Graph learning Matrix-variate data Auto-regressive models homotopy algorithms

来源：评论

学校读者我要写书评

暂无评论

Complexity of Sparse Polynomial Solving: homotopy on Toric Varieties and the Condition Metric

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2019年第1期19卷 1-53页

作者： Malajovich, Gregorio Univ Fed Rio de Janeiro Inst Matemat Dept Matemat Aplicada Caixa Postal 68530 BR-21941909 Rio De Janeiro RJ Brazil

This paper investigates the cost of solving systems of sparse polynomial equations by homotopy continuation. First, a space of systems of n-variate polynomial equations is specified through n monomial bases. The natural locus for the roots of those systems is known to be a certain toric variety. This variety is a compactification of (C\{0})n, dependent on the monomial bases. A toric Newton operator is defined on that toric variety. Smale's alpha theory is generalized to provide criteria of quadratic convergence. Two condition numbers are defined, and a higher derivative estimate is obtained in this setting. The Newton operator and related condition numbers turn out to be invariant through a group action related to the momentum map. A homotopy algorithm is given and is proved to terminate after a number of Newton steps which is linear on the condition length of the lifted homotopy path. This generalizes a result from Shub (Found Comput Math 9(2):171-178, 2009. 10.1007/s10208-007-9017-6).

关键词： Sparse polynomials BKK bound Newton iteration Toric varieties Momentum map homotopy algorithms

来源：评论

学校读者我要写书评

暂无评论

COMPUTATIONAL-COMPLEXITY OF A PIECEWISE LINEAR homotopy ALGORITHM

引用

MATHEMATICAL PROGRAMMING 1984年第2期28卷 164-173页

作者： SAIGAL, R Northwestern University 60201 Evanston IL USA

We give a bound on the number of steps required by the piecewise linear algorithm based on component wise homotopy (proposed by the author for structured problems) when solving a linear problem. When the coefficient matrix is symmetric and positive definite, this bound is polynomial inn and linear in the condition number of the matrix. We also investigate the expected value of the bound for a particular distribution of such matrices.

关键词： Computational Complexity homotopy algorithms Average Behavior Worst Case Behavior

来源：评论

学校读者我要写书评

暂无评论

Complexity of sparse polynomial solving 2: renormalization

引用

IMA JOURNAL OF NUMERICAL ANALYSIS 2023年第4期43卷 2001-2114页

作者： Malajovich, Gregorio Univ Fed Rio de Janeiro Inst Matemat Dept Matemat Aplicada Caixa Postal 68530 BR-21941909 Rio De Janeiro RJ Brazil

Renormalized homotopy continuation on toric varieties is introduced as a tool for solving sparse systems of polynomial equations or sparse systems of exponential sums. The cost of continuation depends on a renormalized condition length, defined as a line integral of the condition number along all the lifted renormalized paths. The theory developed in this paper leads to a continuation algorithm tracking all the solutions between two generic systems with the same structure. The algorithm is randomized, in the sense that it follows a random path between the two systems. The probability of success is one. In order to produce an expected cost bound, several invariants depending solely on the supports of the equations are introduced. For instance, the mixed area is a quermassintegral that generalizes surface area in the same way that mixed volume generalizes ordinary volume. The facet gap measures for each 1-cone in the fan and for each support polytope, how close is the supporting hyperplane to the nearest vertex. Once the supports are fixed, the expected cost depends on the input coefficients solely through two invariants: the renormalized toric condition number and the imbalance of the absolute values of the coefficients. This leads to a nonuniform polynomial complexity bound for polynomial solving in terms of those two invariants.

关键词： sparse polynomials mixed volume mixed area Newton iteration homotopy algorithms toric varieties toric infinity renormalization condition length

来源：评论

学校读者我要写书评

暂无评论

Numerical solution of spacecraft pursuit-Evasion-Capture game based on progressive shooting method

引用

PROCEEDINGS OF THE INSTITUTION OF MECHANICAL ENGINEERS PART G-JOURNAL OF AEROSPACE ENGINEERING 2023年第12期237卷 2874-2886页

作者： Liao, Tian Li, Shunli Chen, Xinlong Zhu, Mengping Harbin Inst Technol Sch Aerosp Harbin Peoples R China China Acad Space Technol Qian Xuesen Space Technol Lab Beijing Peoples R China China Acad Space Technol Intelligent Game & Decis Lab Qian Xuesen Lab Space Technol Beijing 100080 Peoples R China

The time optimal pursuit-evasion-capture (PEC) game problem for two spacecraft with continuous constant thrust is studied, which is a typical and considerable game scenario in practice. Progressive Shooting Method (PSM) is proposed to solve the PEC game in this paper. The method solves the problem in two stages. First-shooting settles a simplified problem by substituting CW dynamics to simple dynamics, while second-shooting settles the original problem with the results of first-shooting. For first-shooting, an analytic initial guess construction method based on prior information is proposed, in which vague adjoint variables are expressed by quantities with clear physical meanings. Through qualitative analysis for the optimal trajectory, the quantities are approximately estimated and then analytic expressions of an initial guess are constructed. The proposed method provides an instructive way to deal with the difficulty that an initial guess is hard to provide for an optimal control problem based on indirect-method. Numerical results show that a PEC game can be solved by the proposed method with well convergence and high computational efficiency.

关键词： pursuit-evasion-capture game optimal control initial guess construction shooting method homotopy algorithms

来源：评论

学校读者我要写书评

暂无评论

RUDIMENTS OF AN AVERAGE CASE COMPLEXITY THEORY FOR PIECEWISE-LINEAR PATH FOLLOWING algorithms

引用

MATHEMATICAL PROGRAMMING 1988年第2期40卷 113-163页

作者： RENEGAR, J 1.School of Operations Research and Industrial Engineering Cornell University 14853 Ithaca NY USA

We examine the efficiency of PL path following algorithms in followingF T -1 (0), whereF T is the PL approximation, induced by the simplicial triangulationT, to a mapf:? n →? n-1. In particular, we consider the prob... 详细信息

We examine the efficiency of PL path following algorithms in followingF _T ^-1 (0), whereF _T is the PL approximation, induced by the simplicial triangulationT, to a mapf:?ⁿ→?^n-1. In particular, we consider the problem of determining an upper bound on the expected number of pivots made per unit length off ^?1(0) that is approximated. We show that if the sizes of the simplices ofT are “sufficiently small”, where “sufficiently small” is an explicitly given quantity dependent on measurements of how “nice”f is, then the average directional density ofT, as introduced by Todd, really does give a good approximation to the expected number of pivots made, confirming what researchers have believed on intuitive grounds for a decade. Because what constitutes “sufficiently small” is a precisely given quantity, i.e., non-asymptotic, we are able to provide some rigorous justification for the claim that the expected number of pivots grows only polynomially inn, the number of variables.

关键词： Average directional density computational complexity homotopy algorithms path following piecewise linear approximations simplicial algorithms triangulations

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：