This dissertation addresses the problem of approximating, in floating-point arithmetic, all real roots (simple, clustered, and multiple) over the unit interval of polynomials in Bernstein form with real coefficients.

No description available.

This dissertation examines the application of various classical root finding methods to digital maximum power point tracking (DMPPT). An overview of root finding methods such as the Newton Raphson Method (NRM), Secant Method (SM), Bisection Method (BSM), Regula Falsi Method (RFM) and a proposed Modified Regula Falsi Method (MRFM) applied to photovoltaic (PV) applications is presented. These methods are compared among themselves. Some of their features are also compared with other commonly used maximum power point (MPP) tracking methods. Issues found when implementing these root finding methods based on continuous variables in a digital domain are explored. Some of these discussed issues include numerical stability, digital implementation of differential operators, and quantization error. Convergence speed is also explored. The analysis is used to provide practical insights into the design of a DMPPT based on classical root finding algorithms. A new DMPPT based on a MRFM is proposed and used as the basis for the discussion. It is shown that this proposed method is faster than the other discussed methods that ensure convergence to the MPP. The discussion is approached from a practical perspective and also includes theoretical analysis to support the observations. Extensive simulation and experimental results with hardware prototypes verify the analysis. / text

我們將原本求只有實根的多項式問題轉換為利用QR方法求一個友矩陣(companion matrix)或是對稱三對角(symmetric tridiagonal matrix)的特徵值問題，在數值測試中顯示出利用傳統演算法去求多項式的根會比求轉換過後矩陣特徵值的方法較沒效率。 / Given a polynomial pn(x) of degree n with real roots, we transform the problem of finding all roots of pn (x) into a problem of finding the eigenvalues of a companion matrix or of a symmetric tridiagonal matrix, which can be done with the QR algorithm. Numerical testing shows that finding the roots of a polynomial by standard algorithms is less efficient than by computing the eigenvalues of a related matrix.

Dans cette thèse, nous nous intéressons à l'étude des structures déterminantielles apparaissent dans l'optimisation semi-définie (SDP), le prolongement naturel de la programmation linéaire au cône des matrices symétrique semi-définie positives. Si l'approximation d'une solution d'un programme semi-défini peut être calculé efficacement à l'aide des algorithmes de points intérieurs, ni des algorithmes exacts efficaces pour la SDP sont disponibles, ni une compréhension complète de sa complexité théorique a été atteinte. Afin de contribuer à cette question centrale en optimisation convexe, nous concevons un algorithme exact pour décider la faisabilité d'une inégalité matricielle linéaire (LMI) $A(x)\succeq 0$. Quand le spectraèdre associé (le lieu $\spec$ des $x \in \RR^n$ ou $A(x)\succeq 0$) n'est pas vide, la sortie de cet algorithme est une représentation algébrique d'un ensemble fini qui contient au moins un point $x \in \spec$: dans ce cas, le point $x$ minimise le rang de $A(x)$ sur $\spec$. La complexité est essentiellement quadratique en le degré de la représentation en sortie, qui coïncide, expérimentalement, avec le degré algébrique de l'optimisation semi-définie. C'est un garantie d'optimalité de cette approche dans le contexte des algorithmes exacts pour les LMI et la SDP. Remarquablement, l'algorithme ne suppose pas la présence d'un point intérieur dans $\spec$, et il profite de l'existence de solutions de rang faible de l'LMI $A(x)\succeq 0$. Afin d'atteindre cet objectif principal, nous développons une approche systématique pour les variétés déterminantielles associées aux matrices linéaires. Nous prouvons que décider la faisabilité d'une LMI $A(x)\succeq 0$ se réduit à calculer des points témoins dans les variétés déterminantielles définies sur $A(x)$. Nous résolvons ce problème en concevant un algorithme exact pour calculer au moins un point dans chaque composante connexe réelle du lieu des chutes de rang de $A(x)$. Cet algorithme prend aussi avantage des structures supplémentaires, et sa complexité améliore l'état de l'art en géométrie algébrique réelle. Enfin, les algorithmes développés dans cette thèse sont implantés dans une nouvelle bibliothèque Maple appelé Spectra, et les résultats des expériences mettant en évidence la meilleure complexité sont fournis. / In this thesis we focus on the study of determinantal structures arising in semidefinite programming (SDP), the natural extension of linear programming to the cone of symetric positive semidefinite matrices. While the approximation of a solution of a semidefinite program can be computed efficiently by interior-point algorithms, neither efficient exact algorithms for SDP are available, nor a complete understanding of its theoretical complexity has been achieved. In order to contribute to this central question in convex optimization, we design an exact algorithm for deciding the feasibility of a linear matrix inequality (LMI) $A(x) \succeq 0$. When the spectrahedron $\spec = \{x \in \RR^n \mymid A(x) \succeq 0\}$ is not empty, the output of this algorithm is an algebraic representation of a finite set meeting $\spec$ in at least one point $x^*$: in this case, the point $x^*$ minimizes the rank of the pencil on the spectrahedron. The complexity is essentially quadratic in the degree of the output representation, which meets, experimentally, the algebraic degree of semidefinite programs associated to $A(x)$. This is a guarantee of optimality of this approach in the context of exact algorithms for LMI and SDP. Remarkably, the algorithm does not assume the presence of an interior point in the spectrahedron, and it takes advantage of the existence of low rank solutions of the LMI. In order to reach this main goal, we develop a systematic approach to determinantal varieties associated to linear matrices. Indeed, we prove that deciding the feasibility of a LMI can be performed by computing a sample set of real solutions of determinantal polynomial systems. We solve this problem by designing an exact algorithm for computing at least one point in each real connected component of the locus of rank defects of a pencil $A(x)$. This algorithm admits as input generic linear matrices but takes also advantage of additional structures, and its complexity improves the state of the art in computational real algebraic geometry. Finally, the algorithms developed in this thesis are implemented in a new Maple library called {Spectra}, and results of experiments highlighting the complexity gain are provided.

Les microARN sont de petits ARN non codants d'environ 22 nucléotides impliqués dans la régulation de l'expression des gènes. Ils ciblent les régions complémentaires des molécules d'ARN messagers que ces gènes codent et ajustent leurs niveaux de traduction en protéines en fonction des besoins de la cellule. En s'attachant à leurs cibles par complémentarité partielle de leurs séquences, ces deux groupes de molécules d'ARN compétitionnent activement pour former des interactions régulatrices. Par conséquent, prédire quantitativement les concentrations d'équilibres des duplexes formés est une tâche qui doit prendre un compte plusieurs facteurs dont l'affinité pour l'hybridation, la capacité à catalyser la cible, la coopérativité et l'accessibilité de l'ARN cible. Dans le modèle que nous proposons, miRBooking 2.0, chaque interaction possible entre un microARN et un site sur un ARN cible pour former un duplexe est caractérisée par une réaction enzymatique. Une réaction de ce type opère en deux phases : une formation réversible d'un complexe enzyme-substrat, le duplexe microARN-ARN, suivie d'une conversion irréversible du substrat en produit, un ARN cible dégradé, et de la restitution l'enzyme qui pourra participer à une nouvelle réaction. Nous montrons que l'état stationnaire de ce système, qui peut comporter jusqu'à 10 millions d'équations en pratique, est unique et son jacobien possède un très petit nombre de valeurs non-nulles, permettant sa résolution efficace à l'aide d'un solveur linéaire épars. Cette solution nous permet de caractériser précisément ce mécanisme de régulation et d'étudier le rôle des microARN dans un contexte cellulaire donné. Les prédictions obtenues sur un modèle de cellule HeLa corrèlent significativement avec un ensemble de données obtenu expérimentalement et permettent d'expliquer remarquablement les effets de seuil d'expression des gènes. En utilisant ces prédictions comme condition initiale et une méthode d'intégration numérique, nous simulons en temps réel la réponse du système aux changements de conditions expérimentales. Nous appliquons ce modèle pour cibler des éléments impliqués dans la transition épithélio-mésenchymateuse (EMT), un mécanisme biologique permettant aux cellules d'acquérir une mobilité essentielle pour proliférer. En identifiant des éléments transcrits différentiellement entre les conditions épithéliale et mésenchymateuse, nous concevons des microARN synthétiques spécifiques pour interférer avec cette transition. Pour ce faire, nous proposons une méthode basée sur une recherche gloutonne parallèle pour rechercher efficacement l'espace de la séquence du microARN et présentons des résultats préliminaires sur des marqueurs connus de l'EMT. / MicroRNAs are small non-coding RNAs of approximately 22 nucleotide long involved in the regulation of gene expression. They target complementary regions to the RNA transcripts molecules that these genes encode and adjust the concentration according to the needs of the cell. As microRNAs and their RNA targets binds each other with imperfect complementarity, these two groups actively compete to form regulatory interactions. Consequently, attempting to quantitatively predict their equilibrium concentrations is a task that must take several factors into account, including the affinity for hybridization, the ability to catalyze the target, cooperation, and RNA accessibility. In the model we propose, miRBooking 2.0, each possible interaction between a microRNA and a binding site on a target RNA is characterized by an enzymatic reaction. A reaction of this type operates in two phases: a reversible formation of an enzyme-substrate complex, the microRNA-RNA duplex, and an irreversible conversion of the substrate in an RNA degradation product that restores the enzyme which can subsequently participate to other reactions. We show that the stationary state of this system, which can include up to 10 million equations in practice, has a very shallow Jacobian, allowing its efficient resolution using a sparse linear solver. This solution allows us to characterize precisely the mechanism of regulation and to study the role of microRNAs in a given cellular context. Predictions obtained on a HeLa S3 cell model correlate significantly with a set of experimental data obtained experimentally and can remarkably explain the expression threshold effects of genes. Using this solution as an initial condition and an explicit method of numerical integration, we simulate in real time the response of the system to changes of experimental conditions. We apply this model to target elements involved in the Epithelio-Mesenchymal Transition (EMT), an important mechanism of tumours proliferation. By identifying differentially expressed elements between the two conditions, we design synthetic microRNAs to interfere with the transition. To do so, we propose a method based on a parallel greedy best-first search to efficiently crawl the sequence space of the microRNA and present preliminary results on known EMT markers.