اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA condition number analysis of an algorithm for solving a system of polynomial equations with one degree of freedom
37
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
This article considers the problem of solving a system of $n$ real polynomial equations in $n+1$ variables. We propose an algorithm based on Newtons method and subdivision for this problem. Our algorithm is intended only for nondegenerate cases, in which case the solution is a 1-dimensional curve. Our first main contribution is a definition of a condition number measuring reciprocal distance to degeneracy that can distinguish poor and well conditioned instances of this problem. (Degenerate problems would be infinitely ill conditioned in our framework.) Our second contribution, which is the main novelty of our algorithm, is an analysis showing that its running time is bounded in terms of the condition number of the problem instance as well as $n$ and the polynomial degrees.
قيم البحث
اقرأ أيضاً
In latest years, several advancements have been made in symbolic-numerical eigenvalue techniques for solving polynomial systems. In this article, we add to this list by reducing the task to an eigenvalue problem in a considerably faster and simpler w
ay than in previous methods. This results in an algorithm which solves systems with isolated solutions in a reliable and efficient way, outperforming homotopy methods in overdetermined cases. We provide an implementation in the proof-of-concept Julia package EigenvalueSolver.jl.
We propose an iterative improvement method for the Harrow-Hassidim-Lloyd (HHL) algorithm to solve a linear system of equations. This is a quantum-classical hybrid algorithm. The accuracy is essential to solve the linear system of equations. However,
the accuracy of the HHL algorithm is limited by the number of quantum bits used to express the eigenvalues of the matrix. Our iterative method improves the accuracy of the HHL solutions, and gives higher accuracy which surpasses the accuracy limited by the number of quantum bits. In practical HHL algorithm, a huge number of measurements is required to obtain good accuracy, even if we provide a sufficient number of quantum bits for the eigenvalue expression, since the solution is statistically processed from the measurements. Our improved iterative method can reduce the number of measurements. Moreover, the sign information for each eigenstate of the solution is lost once the measurement is made, although the sign is significant. Therefore, the naive iterative method of the HHL algorithm may slow down, especially, when the solution includes wrong signs. In this paper, we propose and evaluate an improved iterative method for the HHL algorithm that is robust against the sign information loss, in terms of the number of iterations and the computational accuracy.
Based on the geometric {it Triangle Algorithm} for testing membership of a point in a convex set, we present a novel iterative algorithm for testing the solvability of a real linear system $Ax=b$, where $A$ is an $m times n$ matrix of arbitrary rank.
Let $C_{A,r}$ be the ellipsoid determined as the image of the Euclidean ball of radius $r$ under the linear map $A$. The basic procedure in our algorithm computes a point in $C_{A,r}$ that is either within $varepsilon$ distance to $b$, or acts as a certificate proving $b ot in C_{A,r}$. Each iteration takes $O(mn)$ operations and when $b$ is well-situated in $C_{A,r}$, the number of iterations is proportional to $log{(1/varepsilon)}$. If $Ax=b$ is solvable the algorithm computes an approximate solution or the minimum-norm solution. Otherwise, it computes a certificate to unsolvability, or the minimum-norm least-squares solution. It is also applicable to complex input. In a computational comparison with the state-of-the-art algorithm BiCGSTAB ({it Bi-conjugate gradient method stabilized}), the Triangle Algorithm is very competitive. In fact, when the iterates of BiCGSTAB do not converge, our algorithm can verify $Ax=b$ is unsolvable and approximate the minimum-norm least-squares solution. The Triangle Algorithm is robust, simple to implement, and requires no preconditioner, making it attractive to practitioners, as well as researchers and educators.
The ellipsoid algorithm is a fundamental algorithm for computing a solution to the system of $m$ linear inequalities in $n$ variables $(P): A^{top}x le u$ when its set of solutions has positive volume. However, when $(P)$ is infeasible, the ellipsoid
algorithm has no mechanism for proving that $(P)$ is infeasible. This is in contrast to the other two fundamental algorithms for tackling $(P)$, namely the simplex method and interior-point methods, each of which can be easily implemented in a way that either produces a solution of $(P)$ or proves that $(P)$ is infeasible by producing a solution to the alternative system $mathrm{({it Alt})}: Alambda= 0$, $u^{top}lambda < 0$, $lambda ge 0$. This paper develops an Oblivious Ellipsoid Algorithm (OEA) that either produces a solution of $(P)$ or produces a solution of $mathrm{({it Alt})}$. Depending on the dimensions and on other natural condition measures, the computational complexity of the basic OEA may be worse than, the same as, or better than that of the standard ellipsoid algorithm. We also present two modifi
In this paper, we study the quantum dynamics of a one degree-of-freedom (DOF) Hamiltonian that is a normal form for a saddle node bifurcation of equilibrium points in phase space. The Hamiltonian has the form of the sum of kinetic energy and potentia
l energy. The bifurcation parameter is in the potential energy function and its effect on the potential energy is to vary the depth of the potential well. The main focus is to evaluate the effect of the depth of the well on the quantum dynamics. This evaluation is carried out through the computation of energy eigenvalues and eigenvectors of the time-independent Schrodinger equations, expectation values and position uncertainties for position coordinate, and Wigner functions.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
