|
|
Approximate Polynomial Greatest Common Divisor
Eliaš, Ján ; Zítko, Jan (advisor) ; Hnětynková, Iveta (referee)
Title: Approximate Polynomial Greatest Common Divisor Author: Ján Eliaš Department: Department of Numerical Mathematics, MFF UK Supervisor: Doc. RNDr. Jan Zítko, CSc., Department of Numerical Mathematics, MFF UK Abstract: The computation of polynomial greatest common divisor (GCD) ranks among basic algebraic problems with many applications. The Euclidean algorithm is the oldest and usual technique for computing GCD. However, the GCD computation problem is ill-posed, particularly when some unknown noise is applied to the polyno- mial coefficients. Since the Euclidean algorithm is unstable, new methods have been extensively studied in recent years. Methods based on the numerical rank estimation represent one group of current meth- ods. Their disadvantage is that the numerical rank cannot be computed reliably due to the sensitivity of singular values on noise. The aim of the work is to overcome the ill-posed sensitivity of GCD computation in the presence of noise. Keywords: AGCD, Sylvester matrix, numerical rank, TLS
|
|
|
Transformace Sylvestrovy matice a výpočet největšího společného dělitele dvou polynomů
Eckstein, Jiří ; Zítko, Jan (advisor) ; Tůma, Miroslav (referee)
In this thesis we study the computation of the greatest common divisor of two polynomials. Firstly, properties of Sylvester matrices are considered as well as their role in computation. We then note, that this approach can be naturally generalized for several polynomials. In the penultimate section, Bézout matrices are studied as an analogy to the Sylvester ones, providing necessary comparison. Extension for more than polynomials is presented here as well. Algorithms corresponding to the individual approaches are presented as well. Finally, the algorithms are implemented in MATLAB and are compared in numerical experiments. Powered by TCPDF (www.tcpdf.org)
|
|
|
Transformace Sylvestrovy matice a výpočet největšího společného dělitele dvou polynomů
Eckstein, Jiří ; Zítko, Jan (advisor) ; Tůma, Miroslav (referee)
In this thesis we study the computation of the greatest common divisor of two polynomials. Firstly, properties of Sylvester matrices are considered as well as their role in computation. We then note, that this approach can be naturally generalized for several polynomials. In the penultimate section, Bézout matrices are studied as an analogy to the Sylvester ones, providing necessary comparison. Extension for more than polynomials is presented here as well. Algorithms corresponding to the individual approaches are presented as well. Finally, the algorithms are implemented in MATLAB and are compared in numerical experiments. Powered by TCPDF (www.tcpdf.org)
|
|
|
Approximate Polynomial Greatest Common Divisor
Eliaš, Ján ; Zítko, Jan (advisor) ; Hnětynková, Iveta (referee)
Title: Approximate Polynomial Greatest Common Divisor Author: Ján Eliaš Department: Department of Numerical Mathematics, MFF UK Supervisor: Doc. RNDr. Jan Zítko, CSc., Department of Numerical Mathematics, MFF UK Abstract: The computation of polynomial greatest common divisor (GCD) ranks among basic algebraic problems with many applications. The Euclidean algorithm is the oldest and usual technique for computing GCD. However, the GCD computation problem is ill-posed, particularly when some unknown noise is applied to the polyno- mial coefficients. Since the Euclidean algorithm is unstable, new methods have been extensively studied in recent years. Methods based on the numerical rank estimation represent one group of current meth- ods. Their disadvantage is that the numerical rank cannot be computed reliably due to the sensitivity of singular values on noise. The aim of the work is to overcome the ill-posed sensitivity of GCD computation in the presence of noise. Keywords: AGCD, Sylvester matrix, numerical rank, TLS
|
|
|
Analýza výpočtu největšího společného dělitele polynomů
Kuřátko, Jan ; Zítko, Jan (advisor) ; Janovský, Vladimír (referee)
In this work, the analysis of the computation of the greatest common divisor of univariate and bivariate polynomials is presented. The whole process is split into three stages. In the first stage, data preprocessing is explained and the resulting better numerical behavior is demonstrated. Next stage is concerned with the problem of the computation of the numerical rank of the Sylvester matrix, from which the degree of the greatest common divisor is obtained. The last stage is the actual algorithm for calculating the greatest common divisor of two polynomials. Furthermore, the underlying theory behind the computation of the greatest common divisor is explained and illustrated on many examples. 1
|
|
| |
guest ::
