To see the other types of publications on this topic, follow the link: Solving polynomial systems of equations.
Dissertations / Theses on the topic 'Solving polynomial systems of equations'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Solving polynomial systems of equations.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Wise, Steven M. "POLSYS_PLP: A Partitioned Linear Product Homotopy Code for Solving Polynomial Systems of Equations." Thesis, Virginia Tech, 1998. http://hdl.handle.net/10919/36933.
Full textAbstract:
Globally convergent, probability-one homotopy methods have proven to be very effective for finding all the isolated solutions to polynomial systems of equations. After many years of development, homotopy path trackers based on probability-one homotopy methods are reliable and fast. Now, theoretical advances reducing the number of homotopy paths that must be tracked, and in the handling of singular solutions, have made probability-one homotopy methods even more practical. This thesis describes the theory behind and performance of the new code POLSYS_PLP, which consists of Fortran 90 modules for finding all isolated solutions of a complex coefficient polynomial system of equations by a probability-one homotopy method. The package is intended to be used in conjunction with HOMPACK90, and makes extensive use of Fortran 90 derived data types to support a partitioned linear product (PLP) polynomial system structure. PLP structure is a generalization of m-homogeneous structure, whereby each component of the system can have a different m-homogeneous structure. POLSYS_PLP employs a sophisticated power series end game for handling singular solutions, and provides support for problem definition both at a high level and via hand-crafted code. Different PLP structures and their corresponding Bezout numbers can be systematically explored before committing to root finding.<br>Master of Science
2
Bard, Gregory V. "Algorithms for solving linear and polynomial systems of equations over finite fields with applications to cryptanalysis." College Park, Md. : University of Maryland, 2007. http://hdl.handle.net/1903/7202.
Full textAbstract:
Thesis (Ph. D.) -- University of Maryland, College Park, 2007.<br>Thesis research directed by: Applied Mathematics and Scientific Computation Program. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.
3
Mohamed, Mohamed Saied Emam. "Improved Strategies for Solving Multivariate Polynomial Equation Systems over Finite Fields." Phd thesis, TU Darmstadt, 2011. https://tuprints.ulb.tu-darmstadt.de/2622/4/Mohamed-Diss.pdf.
Full textAbstract:
One of the important research problems in cryptography is the problem of solving multivariate polynomial equations over finite fields. The hardness of solving this problem is the measure of the security of many public key cryptosystems as well as of many symmetric cryptosystems, like block and stream ciphers. In recent years, algebraic cryptanalysis has been presented as a method of attacking cryptosystems. This method consists in solving multivariate polynomial systems. Therefore, developing algorithms for solving such systems is a hot research topic.
Over the recent years, several algorithms have been proposed to solve multivariate polynomial systems over finite fields. A very promising type of these algorithms is based on enlarging a system by generating additional equations and using linear algebra techniques to obtain a solution. Theoretical complexity estimates have shown that algebraic attacks made using these algorithms are infeasible for many realistic applications. This is due to the fact that, in many practical cases, the computations made by these algorithms require a lot of time and memory resources. A big challenge is to improve this algorithm in order to be able to use the limited available memory and time resources to solve large multivariate polynomial systems which exist in practice.
In this thesis we propose strategies to improve the enlargement step of these algorithms. We apply these strategies to the well studied XL algorithm, due to its simple structure, and show that combining these strategies with XL makes it highly competitive to the state-of-the-art algorithms.
In 2006, Jintai Ding presented the concept of mutant polynomials . Mutants are polynomials of a lower degree than expected that appear during the linear algebra
step of XL. The MutantXL algorithm presented in this thesis uses the concept of mutants to improve the solving process of the XL algorithm. The MXL2 algorithm is introduced as an improved version of the MutantXL algorithm by developing a partial enlargement strategy. Specifically, we modify MutantXL in a way such that when it enlarges the system, it partitions the set of polynomials of the maximal degree D into some subsets using a special criteria. After that it explores this set of polynomials, one subset at a time, without being forced to store the whole set at once. This results in solving systems with fewer number of enlarged polynomials than MutantXL.
The main drawback of MXL2, as well as XL and MutantXL algorithms, is that it can solve only systems having a unique solution. In order to solve systems with a finite number of solutions, we present a new sufficient condition for a set of polynomials to be a Gröbner basis . We used this new condition as a termination criteria for the MXL2 algorithm. This modification together with further improvements to the enlargement step of MXL2 are introduced in the MXL3 algorithm for computing Gröbner bases. This thesis also introduces the MGB algorithm which uses a flexible partial enlargement strategy to provide an important improvement to MXL3. The preliminary study presented at the end of the thesis suggests a new upper bound for the complexity of computing Gröbner bases which motivates thinking of new paradigms for estimating the complexity of Gröbner bases computation.
The results in this thesis show that the proposed strategies dramatically improve the performance of the XL algorithm and, moreover, introduce algorithms that outperform Magma’s implementation of F4, one of the currently most efficient algorithms, in terms of time and memory consumption in many cases. Moreover, an adapted version of MutantXL is used to attack the MQQ cryptosystem faster and uses less memory than attacks using F4.
4
Mohamed, Mohamed Saied Emam [Verfasser], Johannes [Akademischer Betreuer] Buchmann, and Jintai [Akademischer Betreuer] Ding. "Improved Strategies for Solving Multivariate Polynomial Equation Systems over Finite Fields / Mohamed Saied Emam Mohamed. Betreuer: Johannes Buchmann ; Jintai Ding." Darmstadt : Universitäts- und Landesbibliothek Darmstadt, 2011. http://d-nb.info/1105562581/34.
Full text
5
Vu, Thi Xuan. "Homotopy algorithms for solving structured determinantal systems." Electronic Thesis or Diss., Sorbonne université, 2020. http://www.theses.fr/2020SORUS478.
Full textAbstract:
Les systèmes polynomiaux multivariés apparaissant dans de nombreuses applications ont des structures spéciales et les systèmes invariants apparaissent dans un large éventail d'applications telles que dans l’optimisation polynomiale et des questions connexes en géométrie algébrique réelle. Le but de cette thèse est de fournir des algorithmes efficaces pour résoudre de tels systèmes structurés. Afin de résoudre le premier type de systèmes, nous concevons des algorithmes efficaces en utilisant les techniques d’homotopie symbolique. Alors que les méthodes d'homotopie, à la fois numériques et symboliques, sont bien comprises et largement utilisées dans la résolution de systèmes polynomiaux pour les systèmes carrés, l'utilisation de ces méthodes pour résoudre des systèmes surdéterminés n'est pas si claire. Hors, les systèmes déterminants sont surdéterminés avec plus d'équations que d'inconnues. Nous fournissons des algorithmes d'homotopie probabilistes qui tirent parti de la structure déterminantielle pour calculer des points isolés dans les ensembles des zéros de tels systèmes. Les temps d'exécution de nos algorithmes sont polynomiaux dans la somme des multiplicités des points isolés et du degré de la courbe d'homotopie. Nous donnons également des bornes sur le nombre de points isolés que nous devons calculer dans trois contextes: toutes les termes de l'entrée sont dans des anneaux polynomiaux classiques, tous ces polynômes sont creux, et ce sont des polynômes à degrés pondérés. Dans la seconde moitié de la thèse, nous abordons le problème de la recherche de points critiques d'une application polynomiale symétrique sur un ensemble algébrique invariant. Nous exploitons les propriétés d'invariance de l'entrée pour diviser l'espace de solution en fonction des orbites du groupe symétrique. Cela nous permet de concevoir un algorithme qui donne une description triangulaire de l'espace des solutions et qui s'exécute en temps polynomial dans le nombre de points que nous devons calculer. Nos résultats sont illustrés par des applications à l'étude d'ensembles algébriques réels définis par des systèmes polynomiaux invariants au moyen de la méthode des points critiques<br>Multivariate polynomial systems arising in numerous applications have special structures. In particular, determinantal structures and invariant systems appear in a wide range of applications such as in polynomial optimization and related questions in real algebraic geometry. The goal of this thesis is to provide efficient algorithms to solve such structured systems. In order to solve the first kind of systems, we design efficient algorithms by using the symbolic homotopy continuation techniques. While the homotopy methods, in both numeric and symbolic, are well-understood and widely used in polynomial system solving for square systems, the use of these methods to solve over-detemined systems is not so clear. Meanwhile, determinantal systems are over-determined with more equations than unknowns. We provide probabilistic homotopy algorithms which take advantage of the determinantal structure to compute isolated points in the zero-sets of determinantal systems. The runtimes of our algorithms are polynomial in the sum of the multiplicities of isolated points and the degree of the homotopy curve. We also give the bounds on the number of isolated points that we have to compute in three contexts: all entries of the input are in classical polynomial rings, all these polynomials are sparse, and they are weighted polynomials. In the second half of the thesis, we deal with the problem of finding critical points of a symmetric polynomial map on an invariant algebraic set. We exploit the invariance properties of the input to split the solution space according to the orbits of the symmetric group. This allows us to design an algorithm which gives a triangular description of the solution space and which runs in time polynomial in the number of points that we have to compute. Our results are illustrated by applications in studying real algebraic sets defined by invariant polynomial systems by the means of the critical point method
6
Paramanathan, Pamini. "Systems of polynomial equations." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2001. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp05/NQ64880.pdf.
Full text
7
Vanatta, Natalie. "Solving multi-variate polynomial equations in a finite field." Monterey, California: Naval Postgraduate School, 2013. http://hdl.handle.net/10945/34756.
Full textAbstract:
Approved for public release; distribution is unlimited<br>Solving large systems of multivariate polynomial equations is an active area of mathematical research, as these polynomials are used in many fields of science. The objective of this research is to advance the development of algebraic methods to attack the mathematical foundations of modern-day encryption methods, which can be modeled as a system of multivariate polynomial equations over a finite field. Our techniques overcome the limitations of previous methods. Additionally, a model is proposed to estimate the time required to solve large systems with our methods. All of these elements were tested successfully on AES and its predecessor, Square. The results showed our techniques to be comparable with a brute force technique. To the best of our knowledge, no other purely algebraic attack on AES has been shown to be this efficient.
8
Stoffel, Joshua David. "Lagrange-Chebyshev Based Single Step Methods for Solving Differential Equations." University of Akron / OhioLINK, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=akron1335299082.
Full text
9
Parts, Inga. "Piecewise polynomial collocation methods for solving weakly singular integro-differential equations /." Online version, 2005. http://dspace.utlib.ee/dspace/bitstream/10062/851/5/parts.pdf.
Full text
10
Cifuentes, Pardo Diego Fernando. "Exploiting chordal structure in systems of polynomial equations." Thesis, Massachusetts Institute of Technology, 2014. http://hdl.handle.net/1721.1/92972.
Full textAbstract:
Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.<br>This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.<br>Cataloged from student-submitted PDF version of thesis.<br>Includes bibliographical references (pages 79-81).<br>Chordal structure and bounded treewidth allow for efficient computation in linear algebra, graphical models, constraint satisfaction and many other areas. Nevertheless, it has not been studied whether chordality might also help solve systems of polynomials. We propose a new technique, which we refer to as chordal elimination, that relies in elimination theory and Gröbner bases. Chordal elimination can be seen as a generalization of sparse linear algebra. Unlike the linear case, the elimination process may not be exact. Nonetheless, we show that our methods are well-behaved for a large family of problems. We also use chordal elimination to obtain a good sparse description of a structured system of polynomials. By maintaining the graph structure in all computations, chordal elimination can outperform standard Gröbner basis algorithms in many cases. In particular, its computational complexity is linear for a restricted class of ideals. Chordal structure arises in many relevant applications and we propose the first method that takes full advantage of it. We demonstrate the suitability of our methods in examples from graph colorings, cryptography, sensor localization and differential equations.<br>by Diego Fernando Cifuentes Pardo.<br>S.M.
11
Sze, Tsz Wo. "On solving univariate polynomial equations over finite fields and some related problems." College Park, Md.: University of Maryland, 2007. http://hdl.handle.net/1903/7632.
Full textAbstract:
Thesis (Ph. D.) -- University of Maryland, College Park, 2007.<br>Thesis research directed by: Dept. of Computer Science. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.
12
SANTOS, ADILIO TITONELI DOS. "SOLVING METHODS OF ALGEBRAIC EQUATIONS AND ANALYSIS OF THE ROOTS OF POLYNOMIAL FUNCTIONS." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2017. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=32358@1.
Full textAbstract:
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO<br>COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR<br>O trabalho apresentou as soluções de equações algébricas polinomiais por radicais e operações elementares nos coeficientes com a pesquisa baseada em livros e artigos; buscou explorar as diversas ideias desenvolvidas nas demonstrações, discussões sobre os casos e os artifícios engenhosos envolvidos, além de algumas demonstrações independentes; foram tratados ainda, os casos especiais onde as raízes estão sujeitas a condições pré estabelecidas e os coeficientes obedecem a uma dada lei; utilizamos a
teoria de Abel-Ruffini e as implicações da teoria de Galois para justificar a
impossibilidade de solução geral por radicais dos polinômios de grau n maior ou igual a 5 e a resposta a
esse impasse com o surgimento de métodos numéricos de aproximação. Essas teorias e os
métodos foram tratados em caráter elementar, por necessitarem de outros trabalhos
detalhados, o que foge do objetivo desta obra. Sendo assim, vimos algoritmos que nos
possibilitam o cálculo, nos casos do primeiro ao quarto graus, das soluções de uma equação
algébrica polinomial além de casos especiais e aproximações numéricas. Utilizamos os
programas de computação algébrica e geometria: Máxima, Geogebra e Maple para as
aproximações, desenhos e gráficos.<br>The work presented the solutions of polynomial algebraic equations by radicals and elementary operations in the coefficients with research based on books and articles; Sought to explore the various ideas developed in the demonstrations, discussions on the cases and ingenious artifacts involved, as well as some independent demonstrations; Were still treated, the special cases where the roots are subject to pre-established conditions and the coefficients obey a given law; We use Abel-Ruffini s theory and the implications of Galois s theory to justify the impossibility of a general solution by radicals of polynomials of degree greater than or equal 5 and the answer to this impasse with the emergence of numerical approximation methods. These theories and methods were treated in an elementary way, because they require other detailed work, which is beyond the scope of this work. Thus, we have seen algorithms that allow us to calculate, in cases from 1st to 4th degrees, the solutions of a polynomial algebraic equation in addition to special cases and numerical approximations. We use the algebraic computing and
geometry programs: Maxima, Geogebra and Maple for approximations, drawings and
graphs.
13
Serna, Rodrigo. "Solving Linear Systems of Equations in Hardware." Thesis, KTH, Skolan för elektro- och systemteknik (EES), 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-200610.
Full text
14
Chen, Jun. "Discrete dynamical systems in solving H-equations." Diss., Virginia Tech, 1995. http://hdl.handle.net/10919/37761.
Full textAbstract:
Three discrete dynamical models are used to solve the Chandrasekhar <i>H</i>-equation with a positive or negative characteristic function. Two of them produce series of continuous functions which converge to the solution of the <i>H</i>-equation. An iteration model of the nth approximation for the <i>H</i>-equation is discussed. This is a nonlinear n-dimensional dynamical system. We study not only the solutions of the nth approximation for the <i>H</i>-equation but also the mathematical structure and behavior of the orbits with respect to the parameter function, i.e. characteristic function. The dynamical system is controlled by a manifold. For n=2, stability of the fixed points is studied. The stable and unstable manifolds passing through the hyperbolically fixed point are obtained. Globally, the bounded orbits region is given. For parameter c in some region a periodic orbit of one dimension will cause periodic orbits in the higher dimensional system. For changing parameter c, the bifurcation points are discussed. For c Ε (-5.6049, 1] the system has a series of double bifurcation points.For <i>c</i> Ε ( -8, -5.6049] chaos appears. For <i>c</i> in a window contained the chaos region, a new bifurcation phenomenon is found. For <i>c</i> ≤7 any periodic orbits appear. For <i>c</i> in the chaos region the behavior of attractor is discussed. Chaos occurs in the n-dimensional dynamical system.<br>Ph. D.
15
Moon, Hyeyoung. "Calculating knot distances and solving tangle equations involving Montesinos links." Diss., University of Iowa, 2010. https://ir.uiowa.edu/etd/859.
Full textAbstract:
My research area is applications of topology to biology, especially DNA topology. DNA topology studies the shape and path of DNA in three dimensional space. My thesis relates to the study of DNA topology in a protein-DNA complex by solving tangle equations and calculating distances between DNA knots.
16
Luttenberger, Michael. "Solving polynomial systems on semirings : a generalization of Newton's method." kostenfrei, 2010. https://mediatum2.ub.tum.de/node?id=796584.
Full text
17
Mou, Chenqi. "Solving polynomial systems over finite fields : Algorithms, Implementations and applications." Paris 6, 2013. http://www.theses.fr/2013PA066805.
Full textAbstract:
Résolution de systèmes polynomiaux sur les corps finis est d’un intérêt particulier en raison de ses applications en Cryptographie, Théorie du Codage, et d’autres domaines de la science de l’information. Dans cette thèse, nous étudions plusieurs aspects importants théoriques et informatiques pour résolution de systèmes polynomiaux sur les corps finis, en particulier sur les deux outils largement utiliss: bases de Gröbner et ensembles triangulaires. Nous proposons des algorithmes efficaces pour le changement de l’ordre des bases de Gröbner d’idéaux de dimension zéro en utilisant le faible densité des matrices de multiplication et d’évaluer telle faible densité pour les systèmes de polynômes génériques. Algorithmes originaux sont présentés pour la décomposition des ensembles de polynômes en ensembles triangulaires simples sur les corps finis. Nous définissons également décomposition sans carré et factorisation des polynômes sur produits non mélangés d’extensions des corps et proposons des lgorithmes pour les calculer. L’efficacité et l’efficience de ces algorithmes ont été vérifiées par des expériences avec nos implémentations. Méthodes de résolution de systèmes polynomiaux sur les corps finis sont également appliquées pour résoudre les problèmes pratiques posés par la Biologie et la Théorie du Codage<br>Polynomial system solving over finite fields is of particular interest because of its applications in Cryptography, Coding Theory, and other areas of information science and technologies. In this thesis we study several important theoretical and computational aspects for solving polynomial systems over finite fields, in particular on the two widely used tools Gröbner bases and triangular sets. We propose efficient algorithms for change of ordering of Gröbner bases of zero-dimensional ideals by using the sparsity of multiplication matrices and evaluate such sparsity for generic polynomial systems. Original algorithms are presented for decomposing polynomial sets into simple triangular sets over finite fields. We also define squarefree decomposition and factorization of polynomials over unmixed products of field extensions and propose algorithms for computing them. The effectiveness and efficiency of these algorithms have been verified by experiments with our implementations. Methods for polynomial system solving over finite fields are also applied to solve practical problems arising from Biology and Coding Theory
18
Tsai, Chih-Hsiung. "Algorithms for solving polynomial systems by homotopy continuation method and its parallelization." Diss., Connect to online resource - MSU authorized users, 2008.
Find full text
19
Smith, Andrew Paul [Verfasser]. "Enclosure Methods for Systems of Polynomial Equations and Inequalities / Andrew Paul Smith." Konstanz : Bibliothek der Universität Konstanz, 2012. http://d-nb.info/1028327854/34.
Full text
20
Duke, Elizabeth R. "Solving higher order dynamic equations on time scales as first order systems." Huntington, WV : [Marshall University Libraries], 2006. http://www.marshall.edu/etd/descript.asp?ref=653.
Full text
21
Lopes, Antonio Roldao. "Accelerating iterative methods for solving systems of linear equations using FPGAs." Thesis, Imperial College London, 2010. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.526401.
Full text
22
Liesen, Jörg. "Construction and analysis of polynomial iterative methods for non-hermitian systems of linear equations." [S.l. : s.n.], 1998. http://deposit.ddb.de/cgi-bin/dokserv?idn=955877776.
Full text
23
Liang, Yu. "The use of parallel polynomial preconditioners in the solution of systems of linear equations." Thesis, University of Ulster, 2005. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.422884.
Full text
24
Clinger, Richard A. "Stability Analysis of Systems of Difference Equations." VCU Scholars Compass, 2007. http://hdl.handle.net/10156/1318.
Full text
25
Odland, Tove. "On Methods for Solving Symmetric Systems of Linear Equations Arising in Optimization." Doctoral thesis, KTH, Optimeringslära och systemteori, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-166675.
Full textAbstract:
In this thesis we present research on mathematical properties of methods for solv- ing symmetric systems of linear equations that arise in various optimization problem formulations and in methods for solving such problems. In the first and third paper (Paper A and Paper C), we consider the connection be- tween the method of conjugate gradients and quasi-Newton methods on strictly convex quadratic optimization problems or equivalently on a symmetric system of linear equa- tions with a positive definite matrix. We state conditions on the quasi-Newton matrix and the update matrix such that the search directions generated by the corresponding quasi-Newton method and the method of conjugate gradients respectively are parallel. In paper A, we derive such conditions on the update matrix based on a sufficient condition to obtain mutually conjugate search directions. These conditions are shown to be equivalent to the one-parameter Broyden family. Further, we derive a one-to-one correspondence between the Broyden parameter and the scaling between the search directions from the method of conjugate gradients and a quasi-Newton method em- ploying some well-defined update scheme in the one-parameter Broyden family. In paper C, we give necessary and sufficient conditions on the quasi-Newton ma- trix and on the update matrix such that equivalence with the method of conjugate gra- dients hold for the corresponding quasi-Newton method. We show that the set of quasi- Newton schemes admitted by these necessary and sufficient conditions is strictly larger than the one-parameter Broyden family. In addition, we show that this set of quasi- Newton schemes includes an infinite number of symmetric rank-one update schemes. In the second paper (Paper B), we utilize an unnormalized Krylov subspace frame- work for solving symmetric systems of linear equations. These systems may be incom- patible and the matrix may be indefinite/singular. Such systems of symmetric linear equations arise in constrained optimization. In the case of an incompatible symmetric system of linear equations we give a certificate of incompatibility based on a projection on the null space of the symmetric matrix and characterize a minimum-residual solu- tion. Further we derive a minimum-residual method, give explicit recursions for the minimum-residual iterates and characterize a minimum-residual solution of minimum Euclidean norm.<br>I denna avhandling betraktar vi matematiska egenskaper hos metoder för att lösa symmetriska linjära ekvationssystem som uppkommer i formuleringar och metoder för en mängd olika optimeringsproblem. I första och tredje artikeln (Paper A och Paper C), undersöks kopplingen mellan konjugerade gradientmetoden och kvasi-Newtonmetoder när dessa appliceras på strikt konvexa kvadratiska optimeringsproblem utan bivillkor eller ekvivalent på ett symmet- risk linjärt ekvationssystem med en positivt definit symmetrisk matris. Vi ställer upp villkor på kvasi-Newtonmatrisen och uppdateringsmatrisen så att sökriktningen som fås från motsvarande kvasi-Newtonmetod blir parallell med den sökriktning som fås från konjugerade gradientmetoden. I den första artikeln (Paper A), härleds villkor på uppdateringsmatrisen baserade på ett tillräckligt villkor för att få ömsesidigt konjugerade sökriktningar. Dessa villkor på kvasi-Newtonmetoden visas vara ekvivalenta med att uppdateringsstrategin tillhör Broydens enparameterfamilj. Vi tar också fram en ett-till-ett överensstämmelse mellan Broydenparametern och skalningen mellan sökriktningarna från konjugerade gradient- metoden och en kvasi-Newtonmetod som använder någon väldefinierad uppdaterings- strategi från Broydens enparameterfamilj. I den tredje artikeln (Paper C), ger vi tillräckliga och nödvändiga villkor på en kvasi-Newtonmetod så att nämnda ekvivalens med konjugerade gradientmetoden er- hålls. Mängden kvasi-Newtonstrategier som uppfyller dessa villkor är strikt större än Broydens enparameterfamilj. Vi visar också att denna mängd kvasi-Newtonstrategier innehåller ett oändligt antal uppdateringsstrategier där uppdateringsmatrisen är en sym- metrisk matris av rang ett. I den andra artikeln (Paper B), används ett ramverk för icke-normaliserade Krylov- underrumsmetoder för att lösa symmetriska linjära ekvationssystem. Dessa ekvations- system kan sakna lösning och matrisen kan vara indefinit/singulär. Denna typ av sym- metriska linjära ekvationssystem uppkommer i en mängd formuleringar och metoder för optimeringsproblem med bivillkor. I fallet då det symmetriska linjära ekvations- systemet saknar lösning ger vi ett certifikat för detta baserat på en projektion på noll- rummet för den symmetriska matrisen och karaktäriserar en minimum-residuallösning. Vi härleder även en minimum-residualmetod i detta ramverk samt ger explicita rekur- sionsformler för denna metod. I fallet då det symmetriska linjära ekvationssystemet saknar lösning så karaktäriserar vi en minimum-residuallösning av minsta euklidiska norm.<br><p>QC 20150519</p>
26
Le, Huu Phuoc. "On solving parametric polynomial systems and quantifier elimination over the reals : algorithms, complexity and implementations." Electronic Thesis or Diss., Sorbonne université, 2021. http://www.theses.fr/2021SORUS554.
Full textAbstract:
La résolution de systèmes polynomiaux est un domaine de recherche actif situé entre informatique et mathématiques. Il trouve de nombreuses applications dans divers domaines des sciences de l'ingénieur (robotique, biologie) et du numérique (cryptographie, imagerie, contrôle optimal). Le calcul formel fournit des algorithmes qui permettent de calculer des solutions exactes à ces applications, ce qui pourraient être très délicat pour des algorithmes numériques en raison de la non-linéarité. La plupart des applications en ingénierie s'intéressent aux solutions réelles. Le développement d'algorithmes permettant de les traiter s'appuie sur les concepts de la géométrie réelle effective ; la classe des ensembles semi-algébriques en constituant les objets de base. Cette thèse se concentre sur trois problèmes ci-dessous, qui apparaissent dans de nombreuses applications et sont largement étudié en calcul formel : - Classifier les solutions réelles d'un système polynomial paramétrique par les valeurs des paramètres; - Élimination de quantificateurs; - Calcul des points isolés d'un ensemble semi-algébrique. Nous concevons de nouveaux algorithmes symboliques avec une meilleure complexité que l'état de l'art. En pratique, nos implémentations efficaces de ces algorithmes sont capables de résoudre des problèmes hors d'atteinte des logiciels de l'état de l'art<br>Solving polynomial systems is an active research area located between computer sciences and mathematics. It finds many applications in various fields of engineering and sciences (robotics, biology, cryptography, imaging, optimal control). In symbolic computation, one studies and designs efficient algorithms that compute exact solutions to those applications, which could be very delicate for numerical methods because of the non-linearity of the given systems. Most applications in engineering are interested in the real solutions to the system. The development of algorithms to deal with polynomial systems over the reals is based on the concepts of effective real algebraic geometry in which the class of semi-algebraic sets constitute the main objects. This thesis focuses on three problems below, which appear in many applications and are widely studied in computer algebra and effective real algebraic geometry: - Classify the real solutions of a parametric polynomial system according to the parameters' value; - Elimination of quantifiers; - Computation of the isolated points of a semi-algebraic set. We designed new symbolic algorithms with better complexity than the state-of-the-art. In practice, our efficient implementations of these algorithms are capable of solving applications beyond the reach of the state-of-the-art software
27
Ahmad, Ab Rahman bin. "The AGE iterative methods for solving large linear systems occurring in differential equations." Thesis, Loughborough University, 1993. https://dspace.lboro.ac.uk/2134/32905.
Full textAbstract:
The work presented in this thesis is wholly concerned with the Alternating Group Explicit (AGE) iterative methods for solving large linear systems occurring in solving Ordinary and Partial Differential Equations (ODEs and PDEs) using finite difference approximations.
28
Donfack, Simplice. "Methods and algorithms for solving linear systems of equations on massively parallel computers." Thesis, Paris 11, 2012. http://www.theses.fr/2012PA112042.
Full textAbstract:
Les processeurs multi-cœurs sont considérés de nos jours comme l'avenir des calculateurs et auront un impact important dans le calcul scientifique. Cette thèse présente une nouvelle approche de résolution des grands systèmes linéaires creux et denses, qui soit adaptée à l'exécution sur les futurs machines pétaflopiques et en particulier celles ayant un nombre important de cœurs. Compte tenu du coût croissant des communications comparé au temps dont les processeurs mettent pour effectuer les opérations arithmétiques, notre approche adopte le principe de minimisation des communications au prix de quelques calculs redondants et utilise plusieurs adaptations pour atteindre de meilleures performances sur les machines multi-cœurs. Nous décomposons le problème à résoudre en plusieurs phases qui sont ensuite mises en œuvre séparément. Dans la première partie, nous présentons un algorithme basé sur le partitionnement d'hypergraphe qui réduit considérablement le remplissage ("fill-in") induit lors de la factorisation LU des matrices creuses non symétriques. Dans la deuxième partie, nous présentons deux algorithmes de réduction de communication pour les factorisations LU et QR qui sont adaptés aux environnements multi-cœurs. La principale contribution de cette partie est de réorganiser les opérations de la factorisation de manière à réduire la sollicitation du bus tout en utilisant de façon optimale les ressources. Nous étendons ensuite ce travail aux clusters de processeurs multi-cœurs. Dans la troisième partie, nous présentons une nouvelle approche d'ordonnancement et d'optimisation. La localité des données et l'équilibrage des charges représentent un sérieux compromis pour le choix des méthodes d'ordonnancement. Sur les machines NUMA par exemple où la localité des données n'est pas une option, nous avons observé qu'en présence de perturbations systèmes (" OS noise"), les performances pouvaient rapidement se dégrader et devenir difficiles à prédire. Pour cela, nous présentons une approche combinant un ordonnancement statique et dynamique pour ordonnancer les tâches de nos algorithmes. Nos résultats obtenues sur plusieurs architectures montrent que tous nos algorithmes sont efficaces et conduisent à des gains de performances significatifs. Nous pouvons atteindre des améliorations de l'ordre de 30 à 110% par rapport aux correspondants de nos algorithmes dans les bibliothèques numériques bien connues de la littérature<br>Multicore processors are considered to be nowadays the future of computing, and they will have an important impact in scientific computing. In this thesis, we study methods and algorithms for solving efficiently sparse and dense large linear systems on future petascale machines and in particular these having a significant number of cores. Due to the increasing communication cost compared to the time the processors take to perform arithmetic operations, our approach embrace the communication avoiding algorithm principle by doing some redundant computations and uses several adaptations to achieve better performance on multicore machines.We decompose the problem to solve into several phases that would be then designed or optimized separately. In the first part, we present an algorithm based on hypergraph partitioning and which considerably reduces the fill-in incurred in the LU factorization of sparse unsymmetric matrices. In the second part, we present two communication avoiding algorithms that are adapted to multicore environments. The main contribution of this part is to reorganize the computations such as to reduce bus contention and using efficiently resources. Then, we extend this work for clusters of multi-core processors. In the third part, we present a new scheduling and optimization approach. Data locality and load balancing are a serious trade-off in the choice of the scheduling strategy. On NUMA machines for example, where the data locality is not an option, we have observed that in the presence of noise, performance could quickly deteriorate and become difficult to predict. To overcome this bottleneck, we present an approach that combines a static and a dynamic scheduling approach to schedule the tasks of our algorithms.Our results obtained on several architectures show that all our algorithms are efficient and lead to significant performance gains. We can achieve from 30 up to 110% improvement over the corresponding routines of our algorithms in well known libraries
29
Bender, Matias Rafael. "Algorithms for sparse polynomial systems : Gröbner bases and resultants." Electronic Thesis or Diss., Sorbonne université, 2019. http://www.theses.fr/2019SORUS029.
Full textAbstract:
La résolution de systèmes polynomiaux est l’un des problèmes les plus anciens et importants en mathématiques informatiques et a des applications dans plusieurs domaines des sciences et de l’ingénierie. C'est un problème intrinsèquement difficile avec une complexité au moins exponentielle du nombre de variables. Cependant, dans la plupart des cas, les systèmes polynomiaux issus d'applications ont une structure quelconque. Dans cette thèse, nous nous concentrons sur l'exploitation de la structure liée à la faible densité des supports des polynômes; c'est-à-dire que nous exploitons le fait que les polynômes n'ont que quelques monômes à coefficients non nuls. Notre objectif est de résoudre les systèmes plus rapidement que les estimations les plus défavorables, qui supposent que tous les termes sont présents. Nous disons qu'un système creux est non mixte si tous ses polynômes ont le même polytope de Newton, et mixte autrement. La plupart des travaux sur la résolution de systèmes creux concernent le cas non mixte, à l'exception des résultants creux et des méthodes d'homotopie. Nous développons des algorithmes pour des systèmes mixtes. Nous utilisons les résultantes creux et les bases de Groebner. Nous travaillons sur chaque théorie indépendamment, mais nous les combinons également: nous tirons parti des propriétés algébriques des systèmes associés à une résultante non nulle pour améliorer la complexité du calcul de leurs bases de Groebner; par exemple, nous exploitons l’exactitude du complexe de Koszul pour déduire un critère d’arrêt précoce et éviter tout les réductions à zéro. De plus, nous développons des algorithmes quasi-optimaux pour décomposer des formes binaires<br>Solving polynomial systems is one of the oldest and most important problems in computational mathematics and has many applications in several domains of science and engineering. It is an intrinsically hard problem with complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. In this thesis we focus on exploiting the structure related to the sparsity of the supports of the polynomials; that is, we exploit the fact that the polynomials only have a few monomials with non-zero coefficients. Our objective is to solve the systems faster than the worst case estimates that assume that all the terms are present. We say that a sparse system is unmixed if all its polynomials have the same Newton polytope, and mixed otherwise. Most of the work on solving sparse systems concern the unmixed case, with the exceptions of mixed sparse resultants and homotopy methods. In this thesis, we develop algorithms for mixed systems. We use two prominent tools in nonlinear algebra: sparse resultants and Groebner bases. We work on each theory independently, but we also combine them to introduce new algorithms: we take advantage of the algebraic properties of the systems associated to a non-vanishing resultant to improve the complexity of computing their Groebner bases; for example, we exploit the exactness of some strands of the associated Koszul complex to deduce an early stopping criterion for our Groebner bases algorithms and to avoid every redundant computation (reductions to zero). In addition, we introduce quasi-optimal algorithms to decompose binary forms
30
Maharani, Maharani. "Enhanced Lanczos algorithms for solving systems of linear equations with embedding interpolation and extrapolation." Thesis, University of Essex, 2015. http://repository.essex.ac.uk/15564/.
Full textAbstract:
Lanczos-type algorithms are prone to breaking down before convergence to an acceptable solution is achieved. This study investigates a number of ways to deal with this issue. In the first instance, we investigate the quality of three types of restarting points in the restarting strategy when applied to a particular Lanczos-type algorithm namely Orthodir. The main contribution of the thesis, however, is concerned with using regression as an alternative way to deal with breakdown. A Lanczos-type algorithm is run for a number of iterations and then stopped, ideally, just before breakdown occurs. The sequence of generated iterates is used to build up a regression model that captures the characteristic of this sequence. The model is then used to generate new iterates that belong to that sequence. Since the iterative process of Lanczos is circumvented, or ignored, while using the model to find new points, the breakdown issue is resolved, at least temporarily, unless convergence is achieved. This new approach, called EIEMLA, is shown formally, through extrapolation, that it generates a new point which is at least as good as the last point generated by the Lanczos-type algorithm prior to stoppage. The remaining part of the thesis reports on the implementation of EIEMLA sequentially and in parallel on a standard parallel machine provided locally and on a Cloud Computing platform, namely Domino Data Lab. Through these implementations, we have shown that problems with up to $10^6$ variables and equations can be solved with the new approach. Extensive numerical results are included in this thesis. Moreover, we point out some important issues for further investigation.
31
Armstrong, Shea. "Suitability of Java for Solving Large Sparse Positive Definite Systems of Equations Using Direct Methods." Thesis, University of Waterloo, 2004. http://hdl.handle.net/10012/1175.
Full textAbstract:
The purpose of the thesis is to determine whether Java, a programming language that evolved out of a research project by Sun Microsystems in 1990, is suitable for solving large sparse linear systems using direct methods. That is, can performance comparable to the language traditionally used for sparse matrix computation, Fortran, be achieved by a Java implementation. Performance evaluation criteria include execution speed and memory requirements. A secondary criterion is ease of development. Many attractive features, unique to the Java programming language, make it desirable for use in sparse matrix computation and provide the motivation for the thesis. The 'write once, run anywhere' proposition, coupled with nearly-ubiquitous Java support, alleviates the need to re-write programs in the event of hardware change. Features such as garbage collection (automatic recycling of memory) and array-index bounds checking make Java programs more robust than those written in Fortran. Java has garnered a poor reputation as a high-performance computing platform, largely attributable to poor performance relative to Fortran in its early years. It is now a consensus among researchers that the Java language itself is not the problem, but rather its implementation. As such, improving compiler technology for numerical codes is critical to achieving high performance in numerical Java applications. Preliminary work involved converting SPARSPAK, a collection of Fortran 90 subroutines for solving large sparse systems of linear equations and least squares problems developed by Dr. Alan George, into Java (J-SPARSPAK). It is well known that the majority of the solution process is spent in the numeric factorization phase. Initial benchmarks showed Java performing, on average, 3. 6 times slower than Fortran for this critical phase. We detail how we improved Java performance to within a factor of two of Fortran.
32
Shramchenko, B. L. "Application of graph theory methods for solving mechatronic tasks." Thesis, Київський національний університет технологій та дизайну, 2018. https://er.knutd.edu.ua/handle/123456789/9715.
Full text
33
Yong, Darryl H. "Solving boundary-value problems for systems of hyperbolic conservation laws with rapidly varying coefficients /." Thesis, Connect to this title online; UW restricted, 2000. http://hdl.handle.net/1773/6760.
Full text
34
Tsankova, Evgenia Kirilova. "Algebraic reasoning of first through third grade students solving systems of two linear equations with two variables." Thesis, Boston University, 2003. https://hdl.handle.net/2144/33575.
Full textAbstract:
Thesis (Ed.D.)--Boston University<br>PLEASE NOTE: Boston University Libraries did not receive an Authorization To Manage form for this thesis or dissertation. It is therefore not openly accessible, though it may be available by request. If you are the author or principal advisor of this work and would like to request open access for it, please contact us at open-help@bu.edu. Thank you.<br>The purpose of the study was to investigate the algebraic reasoning of first through third grade subjects solving systems of two linear equations with two variables. The population consisted of 60 subjects, 20 from each of the grades, 1, 2, and 3, in an elementary school in a suburban city in Massachusetts. To assess algebraic reasoning abilities, the Assessment of Students' Equation Solving Abilities (ASESA) instrument was developed, one version for each grade level. In ASESA, three types of systems of equations were presented in three contexts: pictures of animals, geometric figures, and letters to represent the variables for a total of nine problems. Variations by grade level were due to the magnitude of the values of the variables.
A predetermined sequence of hints was developed to be used in the event that subjects could not solve the problems independently. The hints were of three types: 1) Look, that focused subjects on key information; 2) Record, that requested subjects to record given problem information; and 3) Solve, that led subjects to the algorithm for solving the problems. Hints were scored for each subject and each problem. Strategies used to solve the problems were coded as algebraic or arithmetic.
Statistical analyses were performed to determine the effect of grade level, problem context, problem type, and solution strategy on solution success when the subjects solved problems independently as well as with assistance in the form of hints. Differences in the numbers of hints of each hint type were also identified and analyzed.
When solving problems both independently and when hints were provided, grade level was a significant factor for solution success. Subjects in Grades 2 and 3 performed significantly better than did subjects in Grade 1. Problem context was not a significant factor for solution success. The type of problem was a significant factor for solution success. Type 3 problems, involving four solutions steps, posed the greatest difficulty for all subjects. Subjects who used algebraic strategies were significantly more successful solving problems of all types and in all contexts than were subjects who used arithmetic strategies.<br>2031-01-01
35
Jonsson, Isak. "Recursive Blocked Algorithms, Data Structures, and High-Performance Software for Solving Linear Systems and Matrix Equations." Doctoral thesis, Umeå : Univ, 2003. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-160.
Full text
36
Yaakub, Abdul Razak Bin. "Computer solution of non-linear integration formula for solving initial value problems." Thesis, Loughborough University, 1996. https://dspace.lboro.ac.uk/2134/25381.
Full textAbstract:
This thesis is concerned with the numerical solutions of initial value problems with ordinary differential equations and covers single step integration methods. focus is to study the numerical the various aspects of Specifically, its main methods of non-linear integration formula with a variety of means based on the Contraharmonic mean (C.M) (Evans and Yaakub [1995]), the Centroidal mean (C.M) (Yaakub and Evans [1995]) and the Root-Mean-Square (RMS) (Yaakub and Evans [1993]) for solving initial value problems. the applications of the second It includes a study of order C.M method for parallel implementation of extrapolation methods for ordinary differential equations with the ExDaTa schedule by Bahoshy [1992]. Another important topic presented in this thesis is that a fifth order five-stage explicit Runge Kutta method or weighted Runge Kutta formula [Evans and Yaakub [1996]) exists which is contrary to Butcher [1987] and the theorem in Lambert ([1991] ,pp 181). The thesis is organized as follows. An introduction to initial value problems in ordinary differential equations and parallel computers and software in Chapter 1, the basic preliminaries and fundamental concepts in mathematics, an algebraic manipulation package, e.g., Mathematica and basic parallel processing techniques are discussed in Chapter 2. Following in Chapter 3 is a survey of single step methods to solve ordinary differential equations. In this chapter, several single step methods including the Taylor series method, Runge Kutta method and a linear multistep method for non-stiff and stiff problems are also considered. Chapter 4 gives a new Runge Kutta formula for solving initial value problems using the Contraharmonic mean (C.M), the Centroidal mean (C.M) and the Root-MeanSquare (RMS). An error and stability analysis for these variety of means and numerical examples are also presented. Chapter 5 discusses the parallel implementation on the Sequent 8000 parallel computer of the Runge-Kutta contraharmonic mean (C.M) method with extrapolation procedures using explicit assignment scheduling Kutta RK(4, 4) method (EXDATA) strategies. A is introduced and the data task new Rungetheory and analysis of its properties are investigated and compared with the more popular RKF(4,5) method, are given in Chapter 6. Chapter 7 presents a new integration method with error control for the solution of a special class of second order ODEs. In Chapter 8, a new weighted Runge-Kutta fifth order method with 5 stages is introduced. By comparison with the currently recommended RK4 ( 5) Merson and RK5(6) Nystrom methods, the new method gives improved results. Chapter 9 proposes a new fifth order Runge-Kutta type method for solving oscillatory problems by the use of trigonometric polynomial interpolation which extends the earlier work of Gautschi [1961]. An analysis of the convergence and stability of the new method is given with comparison with the standard Runge-Kutta methods. Finally, Chapter 10 summarises and presents conclusions on the topics discussed throughout the thesis.
37
BUENO, ANDRE LUIS CAVALCANTI. "SOLVING LARGE SYSTEMS OF LINEAR EQUATIONS ON MULTI-GPU CLUSTERS USING THE CONJUGATE GRADIENT METHOD IN OPENCLTM." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2013. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=22099@1.
Full textAbstract:
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO<br>COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR<br>Sistemas de equações lineares esparsos e de grande porte aparecem
como resultado da modelagem de vários problemas nas engenharias. Dada
sua importância, muitos trabalhos estudam métodos para a resolução
desses sistemas. Esta dissertação explora o potencial computacional de
múltiplas GPUs, utilizando a tecnologia OpenCL, com a finalidade de
resolver sistemas de equações lineares de grande porte. Na metodologia
proposta, o método do gradiente conjugado é subdivido em kernels que
são resolvidos por múltiplas GPUs. Para tal, se fez necessário compreender
como a arquitetura das GPUs se relaciona com a tecnologia OpenCL a fim
de obter um melhor desempenho.<br>The process of modeling problems in the engineering fields tends to
produce substantiously large systems of sparse linear equations. Extensive
research has been done to devise methods to solve these systems. This
thesis explores the computational potential of multiple GPUs, through
the use of the OpenCL tecnology, aiming to tackle the solution of large
systems of sparse linear equations. In the proposed methodology, the
conjugate gradient method is subdivided into kernels, which are delegated
to multiple GPUs. In order to achieve an efficient method, it was necessary
to understand how the GPUs’ architecture communicates with OpenCL.
38
Souza, Adão Gomes de. "Resolução de equações via métodos numéricos: bissecção e falsa posição." Universidade Federal de Goiás, 2017. http://repositorio.bc.ufg.br/tede/handle/tede/8079.
Full textAbstract:
Submitted by Franciele Moreira (francielemoreyra@gmail.com) on 2017-12-27T12:13:05Z
No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Dissertação - Adão Gomes de Souza - 2017.pdf: 2241174 bytes, checksum: f485f691848f41537c07408e1c5b96ad (MD5)<br>Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-12-28T09:30:56Z (GMT) No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Dissertação - Adão Gomes de Souza - 2017.pdf: 2241174 bytes, checksum: f485f691848f41537c07408e1c5b96ad (MD5)<br>Made available in DSpace on 2017-12-28T09:30:56Z (GMT). No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Dissertação - Adão Gomes de Souza - 2017.pdf: 2241174 bytes, checksum: f485f691848f41537c07408e1c5b96ad (MD5)
Previous issue date: 2017-11-23<br>Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES<br>The main objective of this work is to discuss in a conceptual way the historical process and evolution of the resolution of algebraic equations. The justification for choosing the theme hovers about its contemporaneity, besides the expectation of contributing to the academic scope. The research method followed is qualitative, with a basic research approach, exploratory nature and information collection through bibliographic research. Among the main findings, it was possible to conclude that algebraic equations arise in the midst of ancient human civilizations, in the man's attempt to measure quantities and solve everyday problems of life. Therefore, it is noted that, unlike the stigma that hangs over the content of mathematics, the science it involves is not far from reality and human experience, but rather a part of it that seeks answers to the common problems of life. What makes math as a whole and the algebraic equations common problems of life that need to be learned and solved.<br>O presente trabalho tem como objetivo central debater de maneira conceitual sobre o processo e evolução histórica da resolução das equações algébricas. A justificativa para a escolha do tema paira sobre sua contemporaneidade, além da expectativa de contribuir para o âmbito acadêmico. O método de pesquisa empreendido segue natureza qualitativa, com abordagem de pesquisa básica, de natureza exploratória e coleta de informações por meio de pesquisa bibliográfica. Dentre os principais achados, foi possível concluir que as equações algébricas surgem em meio a civilizações humanas antigas, na tentativa do homem de mensurar quantidades e resolver problemas cotidianos da vida. Portanto, nota-se que, diferente do estigma que paira sobre o conteúdo da matemática, a ciência que envolve não é distante da realidade e da experiência humana, mas sim, uma parte dela que busca respostas aos problemas comuns da vida. O que faz da matemática como um todo e das equações algébricas, problemáticas comuns da vida e que precisam ser aprendidos e solucionados.
39
Passos, Livia Novaes Teixeira. "Soluções analíticas e numéricas de equações polinomiais." Universidade de São Paulo, 2017. http://www.teses.usp.br/teses/disponiveis/55/55136/tde-02022018-092819/.
Full textAbstract:
As equações polinomiais são estudadas desde a antiguidade e atualmente são utilizadas, por exemplo, para modelar problemas do cotidiano nas mais variadas áreas do conhecimento. As técnicas de solução de equações polinomiais nem sempre são triviais, principalmente quando envolvem equações de alta ordem e raízes complexas. O ensino desse tema no Ensino Básico é limitado a equações de segundo ou terceiro grau e coeficientes inteiros, o que restringe a aplicação em problemas mais realistas. Assim, o objetivo deste trabalho é trazer uma contribuição aos estudantes, aos professores do Ensino Básico e aos demais interessados, apresentando um material que aborde técnicas de resolução para equação polinomial de diversas naturezas. Iniciamos por uma revisão dos números complexos e dos polinômios, suas operações e propriedades. Embasamos o trabalho com teoremas e permeamos de exemplos com um crescente grau de dificuldade. Dividimos as técnicas de resolução em analíticas e numéricas. Entre as primeiras, tratamos das relações de Girard, das fórmulas resolventes e de alguns casos particulares de equações. Entre as técnicas numéricas, estudamos o método de Newton, o método das secantes e o método de Newton-Bairstow, este último para encontrar raízes complexas.<br>Polynomial equations have been studied since antiquity and are currently used, for example, to model everyday problems in the most varied areas of knowledge. The solution techniques of polynomial equations are not always trivial, especially when they involve high order equations and complex roots. The teaching of this subject in Basic Education is limited to second or third degree equations and integer coefficients, which restricts the application to more realistic problems. Thus, the objective of this work is to bring a contribution to students, teachers of Basic Education and other interested parties, presenting a material that treats of resolution techniques for polynomial equation of different natures. We begin with a review of complex numbers and polynomials, their operations and properties. We support the work with theorems and permeate examples with an increasing degree of difficulty. We divide the techniques of resolution into analytical and numerical. Among the first, we deal with Girards relations, the resolvent formulas, and some particular cases of equations. Among numerical techniques, we studied the Newton method, the secant method, and the Newton-Bairstow method, the last one to find complex roots.
40
Anderson, Curtis James. "Estimating the Optimal Extrapolation Parameter for Extrapolated Iterative Methods When Solving Sequences of Linear Systems." University of Akron / OhioLINK, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=akron1383826559.
Full text
41
Eggers, Andreas [Verfasser], Martin [Akademischer Betreuer] Fränzle, and Nacim [Akademischer Betreuer] Ramdani. "Direct handling of ordinary differential equations in constraint-solving-based analysis of hybrid systems / Andreas Eggers. Betreuer: Martin Fränzle ; Nacim Ramdani." Oldenburg : BIS der Universität Oldenburg, 2014. http://d-nb.info/1056999748/34.
Full text
42
Molina, Aristizabal Sergio D. "Semi-Regular Sequences over F2." University of Cincinnati / OhioLINK, 2015. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1445342810.
Full text
43
Hays, Joseph T. "Parametric Optimal Design Of Uncertain Dynamical Systems." Diss., Virginia Tech, 2011. http://hdl.handle.net/10919/28850.
Full textAbstract:
This research effort develops a comprehensive computational framework to support the parametric optimal design of uncertain dynamical systems. Uncertainty comes from various sources, such as: system parameters, initial conditions, sensor and actuator noise, and external forcing. Treatment of uncertainty in design is of paramount practical importance because all real-life systems are affected by it; not accounting for uncertainty may result in poor robustness, sub-optimal performance and higher manufacturing costs.
Contemporary methods for the quantification of uncertainty in dynamical systems are computationally intensive which, so far, have made a robust design optimization methodology prohibitive. Some existing algorithms address uncertainty in sensors and actuators during an optimal design; however, a comprehensive design framework that can treat all kinds of uncertainty with diverse distribution characteristics in a unified way is currently unavailable. The computational framework uses Generalized Polynomial Chaos methodology to quantify the effects of various sources of uncertainty found in dynamical systems; a Least-Squares Collocation Method is used to solve the corresponding uncertain differential equations. This technique is significantly faster computationally than traditional sampling methods and makes the construction of a parametric optimal design framework for uncertain systems feasible.
The novel framework allows to directly treat uncertainty in the parametric optimal design process. Specifically, the following design problems are addressed: motion planning of fully-actuated and under-actuated systems; multi-objective robust design optimization; and optimal uncertainty apportionment concurrently with robust design optimization. The framework
advances the state-of-the-art and enables engineers to produce more robust and optimally performing designs at an optimal manufacturing cost.<br>Ph. D.
44
Muševič, Sašo. "Non-stationary sinusoidal analysis." Doctoral thesis, Universitat Pompeu Fabra, 2013. http://hdl.handle.net/10803/123809.
Full textAbstract:
Muchos tipos de señales que encontramos a diario pertenecen a la categoría de sinusoides no estacionarias. Una gran parte de esas señales son sonidos que presentan una gran variedad de características: acústicos/electrónicos, sonidos instrumentales harmónicos/impulsivos, habla/canto, y la mezcla de todos ellos que podemos encontrar en la música. Durante décadas la comunidad científica ha estudiado y analizado ese tipo de señales. El motivo principal es la gran utilidad de los avances científicos en una gran variedad de áreas, desde aplicaciones médicas, financiera y ópticas, a procesado de radares o sonar, y también a análisis de sistemas. La estimación precisa de los parámetros de sinusoides no estacionarias es una de las tareas más comunes en procesado digital de señales, y por lo tanto un elemento fundamental e indispensable para una gran variedad de aplicaciones.
Las transformaciones de tiempo y frecuencia clásicas son solamente apropiadas para señales con variación lenta de amplitud y frecuencia. Esta suposición no suele cumplirse en la práctica, lo que conlleva una degradación de calidad y la aparición de artefactos. Además, la resolución temporal y frecuencial no se puede incrementar arbitrariamente debido al conocido principio de incertidumbre de Heisenberg. \\
El principal objetivo de esta tesis es revisar y mejorar los métodos existentes para el análisis de sinusoides no estacionarias, y también proponer nuevas estrategias y aproximaciones. Esta disertación contribuye sustancialmente a los análisis sinusoidales existentes: a) realiza una evaluación crítica del estado del arte y describe con gran detalle los métodos de análisis existentes, b) aporta mejoras sustanciales a algunos de los métodos existentes más prometedores, c) propone varias aproximaciones nuevas para el análisis de los modelos sinusoidales existentes i d) propone un modelo sinusoidal muy general y flexible con un algoritmo de análisis directo y rápido.<br>Many types of everyday signals fall into the non-stationary sinusoids category. A large family of such signals represent audio, including acoustic/electronic, pitched/transient instrument sounds, human speech/singing voice, and a mixture of all: music. Analysis of such signals has been in the focus of the research community for decades. The main reason for such intense focus is the wide applicability of the research achievements to medical, financial and optical applications, as well as radar/sonar signal processing and system analysis. Accurate estimation of sinusoidal parameters is one of the most common digital signal processing tasks and thus represents an indispensable building block of a wide variety of applications.
Classic time-frequency transformations are appropriate only for signals with slowly varying amplitude and frequency content - an assumption often violated in practice. In such cases, reduced readability and the presence of artefacts represent a significant problem. Time and frequency resolu
45
Trad, Farah. "Stability of some hyperbolic systems with different types of controls under weak geometric conditions." Electronic Thesis or Diss., Valenciennes, Université Polytechnique Hauts-de-France, 2024. http://www.theses.fr/2024UPHF0015.
Full textAbstract:
Le but de cette thèse est d'étudier la stabilisation de certaines équations d'évolution du second ordre. Tout d’abord, nous nous concentrons sur l’étude de la stabilisation d’équations d’évolution du second ordre de type hyperbolique localement faiblement couplées, caractérisées par un amortissement direct dans une seule des deux équations. Comme de tels systèmes ne sont pas exponentiellement stables, nous souhaitons déterminer les taux de décroissance de l’énergie polynomiale. Nos principales contributions concernent les propriétés abstraites de stabilité forte et polynomiale, qui sont dérivées des propriétés de stabilité de deux problèmes auxiliaires : l'équation avec amortissement unique et l'équation avec amortissement liée à l'opérateur de couplage. La principale nouveauté est que les taux de décroissance d'énergie polynomiale sont obtenus dans plusieurs situations importantes non abordées auparavant, y compris le cas où l'opérateur de couplage n'est ni partiellement coercitif ni nécessairement limité. Les principaux outils utilisés dans notre étude sont l’approche du domaine fréquentiel combinée à une nouvelle technique de multiplicateurs basée sur les solutions des équations résolvantes des problèmes auxiliaires susmentionnés. Le cadre abstrait développé est ensuite illustré par plusieurs exemples concrets non traités auparavant. Ensuite, la stabilisation d'une équation de plaque de Kirchhoff bidimensionnelle avec des conditions aux limites acoustiques généralisées est examinée. En employant une approche spectrale combinée à un critère général d'Arendt-Batty, nous établissons d'abord la forte stabilité de notre modèle. Nous prouvons ensuite que le système ne se dégrade pas de façon exponentielle. Cependant, à condition que les coefficients des conditions aux limites acoustiques satisfassent à certaines hypothèses, nous prouvons que l'énergie satisfait à différents taux de décroissance de l'énergie polynomiale en fonction du comportement de notre système auxiliaire. Nous étudions également le taux de décroissance sur les domaines satisfaisant aux conditions aux limites du multiplicateur. De plus, nous présentons quelques exemples appropriés et montrons que nos hypothèses ont été correctement définies. Enfin, nous considérons un problème de transmission d'ondes avec des conditions aux limites acoustiques généralisées dans un espace unidimensionnel, dont nous étudions la stabilité théoriquement et numériquement. Dans la partie théorique nous prouvons que notre système est fortement stable. Nous présentons ensuite divers taux de décroissance d'énergie polynomiale, à condition que les coefficients des conditions aux limites acoustiques satisfassent certaines hypothèses, nous donnons des exemples pertinents pour montrer que nos hypothèses sont correctes. Dans la partie numérique, nous étudions une approximation numérique de notre système utilisant la discrétisation en volumes finis dans un schéma à variables spatiales et différences finies dans le temps<br>The purpose of this thesis is to investigate the stabilization of certain second order evolution equations. First, we focus on studying the stabilization of locally weakly coupled second order evolution equations of hyperbolic type, characterized by direct damping in only one of the two equations. As such systems are not exponentially stable , we are interested in determining polynomial energy decay rates. Our main contributions concern abstract strong and polynomial stability properties, which are derived from the stability properties of two auxiliary problems: the sole damped equation and the equation with a damping related to the coupling operator. The main novelty is thatthe polynomial energy decay rates are obtained in several important situations previously unaddressed, including the case where the coupling operator is neither partially coercive nor necessarily bounded. The main tools used in our study are the frequency domain approach combined with new multipliers technique based on the solutions of the resolvent equations of the aforementioned auxiliary problems. The abstract framework developed is then illustrated by several concrete examples not treated before. Next, the stabilization of a two-dimensional Kirchhoff plate equation with generalized acoustic boundary conditions is examined. Employing a spectrum approach combined with a general criteria of Arendt-Batty, we first establish the strong stability of our model. We then prove that the system doesn't decay exponentially. However, provided that the coefficients of the acoustic boundary conditions satisfy certain assumptions we prove that the energy satisfies varying polynomial energy decay rates depending on the behavior of our auxiliary system. We also investigate the decay rate on domains satisfying multiplier boundary conditions. Further, we present some appropriate examples and show that our assumptions have been set correctly. Finally, we consider a wave wave transmission problem with generalized acoustic boundary conditions in one dimensional space, where we investigate the stability theoretically and numerically. In the theoretical part we prove that our system is strongly stable. We then present diverse polynomial energy decay rates provided that the coefficients of the acoustic boundary conditions satisfy some assumptions. we give relevant examples to show that our assumptions are correct. In the numerical part, we study a numerical approximation of our system using finite volume discretization in a spatial variable and finite difference scheme in time
46
Camargos, Ana Flávia Peixoto de. "Computação paralela em GPU para resolução de sistemas de equações algébricas resultantes da aplicação do método de elementos finitos em eletromagnetismo." Universidade de São Paulo, 2014. http://www.teses.usp.br/teses/disponiveis/3/3143/tde-29042015-181255/.
Full textAbstract:
Este trabalho apresenta a aplicação de técnicas de processamento paralelo na resolução de equações algébricas oriundas do Método de Elementos Finitos aplicado ao Eletromagnetismo, nos regimes estático e harmônico. As técnicas de programação paralelas utilizadas foram OpenMP, CUDA e GPUDirect, sendo esta última para as plataformas do tipo Multi-GPU. Os métodos iterativos abordados incluem aqueles do subespaço Krylov: Gradientes Conjugados, Gradientes Biconjugados, Conjugado Residual, Gradientes Biconjugados Estabilizados, Gradientes Conjugados para equações normais (CGNE e CGNR) e Gradientes Conjugados ao Quadrado. Todas as implementações fizeram uso das bibliotecas CUSP, CUSPARSE e CUBLAS. Para problemas estáticos, os seguintes pré-condicionadores foram adotados, todos eles com implementações paralelizadas e executadas na GPU: Decomposições Incompletas LU e de Cholesky, Multigrid Algébrico, Diagonal e Inversa Aproximada. Para os problemas harmônicos, apenas os dois primeiros pré-condicionadores foram utilizados, porém na sua versão sequencial, com execução na CPU, resultando em uma implementação híbrida CPU-GPU. As ferramentas computacionais desenvolvidas foram testadas na simulação de problemas de aterramento elétrico. No caso do regime harmônico, em que o fenômeno é regido pela Equação de Onda completa com perdas e não homogênea, a formulação adotada foi aquela em dois potenciais, A-V aresta-nodal. Em todas as situações, os aplicativos desenvolvidos para GPU apresentaram speedups apreciáveis, demonstrando a potencialidade dessa tecnologia para a simulação de problemas de larga escala na Engenharia Elétrica, com excelente relação custo-benefício.<br>This work presents the use of parallel processing techniques in Graphics Processing Units (GPU) for the solution of algebraic equations arising from the Finite Element modeling of electromagnetic phenomena, both in steadystate and time-harmonic regime. The techniques used were parallel programming OpenMP, CUDA and GPUDirect, the latter for those platforms of type Multi-GPU. The iterative methods discussed include those of the Krylov subspace: Conjugate Gradients, Bi-conjugate Gradients, Conjugate Residual, Bi-conjugate Gradients Stabilized, Conjugate Gradients for Normal Equations (CGNE and CGNR) and Conjugate Gradients Squared. All implementations have made use of CUSP, CUSPARSE and CUBLAS libraries. For the static problems, the following pre-conditioners were adopted, all with parallelized implementations and executed on the GPU: Incomplete decompositions, both LU and Cholesky, Algebraic Multigrid, Diagonal and Approximate Inverse. For the time-harmonic varying problems, only the first two pre-conditioners were used, but in their sequential version and running in the CPU, which yielded a hybrid CPU-GPU implementation. The developed computational tools were tested in the simulation of electrical grounding systems. In the case of the harmonic regime, in which the phenomenon is governed by the driven, lossy wave equation, the formulation adopted was that in two potential, the ungauged edge A-V formulation. In all cases, the developed GPU-based tools showed considerable speedups, showing that this is a promising technology for the simulation of large-scale Electrical Engineering problems, with excellent cost-benefit.
47
Goulart, Andreza Martins Antunes. "A aprendizagem significativa de sistemas de equações do 1º grau por meio da resolução de problemas." Pontifícia Universidade Católica de São Paulo, 2014. https://tede2.pucsp.br/handle/handle/10997.
Full textAbstract:
Made available in DSpace on 2016-04-27T16:57:31Z (GMT). No. of bitstreams: 1
Andreza Martins Antunes Goulart.pdf: 2398545 bytes, checksum: 47ce4c98a255655ad07a08f56d9c829f (MD5)
Previous issue date: 2014-06-10<br>Coordenação de Aperfeiçoamento de Pessoal de Nível Superior<br>This study aims to investigate whether the teaching and learning of equations of the 1st grade students from the 8th grade of elementary school systems, by means of solving problems allied to the principles of meaningful learning can contribute to an effective knowledge construction. This is a qualitative study, conducted by a teaching intervention has been proposed in which a sequence of activities, and data were collected through observation and classroom notes and analysis of students' protocols. The survey was conducted with students from the 8th grade of Elementary School from a private institution in the city of São Paulo, in which the researcher is a teacher. The content that was being developed at that time was the 1st degree equations systems with two unknowns, and the teaching methodology adopted by the teacher was focused on teaching mathematics through problem solving. The didactic proposal for this work was to introduce the contents of the system of equations by means of a sequence of activities, all developed in mathematics classrooms. From what was already known by the students, they solve the issues proposed in different situations, representing them by means of equations with two unknowns and adopting two different methods for the solution: the addition and replacement. The analysis of the protocols of students and notes taken during development activities indicates that students have noted that the proposals situations, the use of equations with two unknowns would require, unlike what happens in an equation of the 1st degree, and that when using the initial letters of words that correspond to the unknown, would facilitate this process. To be developed both methods of resolution, addition and substitution, students, despite some resistance presented by the second method, the end realized that, for different situations, one of the methods could facilitate the resolution of the proposed issue. After the completion and analysis of the instructional sequence , it can be concluded that teaching through problem solving contributes to greater understanding of what is being done and that this approach allows students to understand why the need to use the system equations of the 1st grade to solve certain situations . The use of each of the unknowns, thereby, as well as the importance of knowing two methods of resolution makes its meaningful learning<br>Esse estudo tem por objetivo investigar se o ensino e a aprendizagem de sistemas de equações do 1º grau por alunos do 8º ano do Ensino Fundamental, por meio de resolução de problemas aliada aos princípios da aprendizagem significativa, podem contribuir para uma eficaz construção de conhecimento. Trata-se de uma pesquisa do tipo qualitativa, realizada por meio de uma intervenção de ensino em que foi proposta uma sequência de atividades, e os dados foram coletados por meio de observação e anotações em sala de aula e análise de protocolos de alunos. A pesquisa foi realizada com alunos do 8º ano do Ensino Fundamental de uma instituição privada da cidade de São Paulo, na qual a pesquisadora é professora. O conteúdo que na época estava sendo desenvolvido era Sistemas de Equações do 1º grau com duas incógnitas, e a metodologia de ensino adotada pelo professor era focada no ensino de Matemática por meio da resolução de problemas. A proposta didática para este trabalho era introduzir o conteúdo de sistema de equações por meio de uma sequência de atividades, todas desenvolvidas nas aulas de Matemática. A partir do que já era de conhecimento dos alunos, estes resolveram as questões propostas em diferentes situações, representando-as por meio de equações com duas incógnitas e adotando dois métodos distintos para obter a solução: da adição e da substituição. A análise dos protocolos dos alunos e das anotações realizadas durante o desenvolvimento das atividades indica que os alunos notaram que, nas situações propostas, seria necessário o uso de equações com duas incógnitas, diferente do que ocorre em uma equação do 1º grau, e que, ao utilizar as letras iniciais das palavras que correspondiam à incógnita, facilitaria esse processo. Ao serem desenvolvidos os dois métodos de resolução, da adição e da substituição, os alunos, apesar de apresentaram certa resistência pelo segundo método, ao final perceberam que, para diferentes situações, um dos métodos poderia facilitar a resolução da questão proposta. Após a realização e análise da sequência didática, pode-se concluir que o ensino por meio da resolução de problemas contribui para maior compreensão do que está sendo feito e que esse tipo de abordagem permite que os alunos compreendam o porquê da necessidade de utilizar o sistema de equações do 1º grau para resolver determinadas situações. O uso de cada uma das incógnitas, desse modo, bem como a importância de conhecer dois métodos de resolução, torna sua aprendizagem significativa
48
Rance, Guillaume. "Commande H∞ paramétrique et application aux viseurs gyrostabilisés." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLS152/document.
Full textAbstract:
Cette thèse porte sur la commande H∞ par loop-shaping pour les systèmes linéaires à temps invariant d'ordre faible avec ou sans retard et dépendant de paramètres inconnus. L'objectif est d'obtenir des correcteurs H∞ paramétriques, c'est-à-dire dépendant explicitement des paramètres inconnus, pour application à des viseurs gyrostabilisés.L'existence de ces paramètres inconnus ne permet plus l'utilisation des techniques numériques classiques pour la résolution du problème H∞ par loop-shaping. Nous avons alors développé une nouvelle méthodologie permettant de traiter les systèmes linéaires de dimension finie grâce à l'utilissation de techniques modernes de calcul formel dédiées à la résolution des systèmes polynomiaux (bases de Gröbner, variétés discriminantes, etc.).Une telle approche présente de multiples avantages: étude de sensibilités du critère H∞ par rapport aux paramètres, identification de valeurs de paramètres singulières ou remarquables, conception de correcteurs explicites optimaux/robustes, certification numérique des calculs, etc. De plus, nous montrons que cette approche peut s'étendre à une classe de systèmes à retard.Plus généralement, cette thèse s'appuie sur une étude symbolique des équations de Riccati algébriques. Les méthodologies génériques développées ici peuvent s'étendre à de nombreux problèmes de l'automatique, notamment la commande LQG, le filtrage de Kalman ou invariant<br>This PhD thesis deals with the H∞ loop-shaping design for low order linear time invariant systems depending on unknown parameters. The objective of the PhD thesis is to obtain parametric H∞ controllers, i.e. controllers which depend explicitly on the unknown model parameters, and to apply them to the stabilization of gyrostabilized sights.Due to the unknown parameters, no numerical algorithm can solve the robust control problem. Using modern symbolic techniques dedicated to the solving of polynomial systems (Gröbner bases, discriminant varieties, etc.), we develop a new methodology to solve this problem for finite-dimensional linear systems.This approach shows several advantages : we can study the sensibilities of the H∞ criterion to the parameter variations, identify singular or remarquable values of the parameters, compute controllers which depend explicitly on the parameters, certify the numerical computations, etc. Furthermore, we show that this approach can be extended to a class of linear time-delay systems.More generally, this PhD thesis develops an algebraic approach for the study of algebraic Riccati equations. Thus, the methodology obtained can be extended to many different problems such as LQG control and Kalman or invariant filtering
49
Kiefer, Stefan [Verfasser]. "Solving systems of positive polynomial equations / Stefan Kiefer." 2009. http://d-nb.info/997741503/34.
Full text
50
Farea, Hussain A. "Solving polynomial equations from 2000 B.C. through 20th century." Thesis, 1994. http://hdl.handle.net/1957/35267.
Full textAbstract:
This paper is divided into two parts. The first part
traces (in details providing proofs and examples) the
history of the solutions of polynomial equations(of the
first, second, third, and fourth degree) by radicals from
Babylonian times (2000 B.C.) through 20th century. Also it
is shown that there is no solution by radicals for the
quintic (fifth degree) and higher degree equations.
The second part of this thesis illustrates both
numerical and graphical solutions of the quintic and higher
degree polynomial equations using modern technology such as
graphics calculators (TI-85, and HP-48G) and software
packages (Matlab, Mathematica, and Maple).<br>Graduation date: 1995