Resumen de Algorithms for curve design and accurate computations with totally positive matrices
This doctoral thesis is framed within the theory of Total Positivity. Totally positive matrices have appeared in applications from fields as diverse as Approximation Theory, Biology, Economics, Combinatorics, Statistics, Differential Equations, Mechanics, Computer Aided Geometric Design or Linear Numerical Algebra. In this thesis, we will focus on two of the fields that are related to totally positive matrices.
On the one hand, this thesis falls within the field of Computer-Aided Geometric Design (CAGD) and, in particular, the study of the representation of curves by means of control polygons. The importance of totally positive matrices comes from the fact that the normalized totally positive systems, whose collocation matrices are totally positive, provide shape preserving representations. The Bernstein basis of polynomials is the most used polynomial basis in CAGD. The collocation matrix of the Bernstein basis is stochastic and totally positive. In fact, the Bernstein basis is the normalized B-basis of its generated space and has the optimal shape preserving properties. The curves defined parametrically by means of this basis, called Bézier curves, are of great interest in CAGD since they provide the representation of polynomial curves with optimal shape preserving properties. The de Casteljau algorithm is a corner cutting algorithm with the property of evaluating the Bézier curve from its control polygon. Another important property of this algorithm is the subdivision property. One of the objectives of this thesis is to find new systems of functions, not necessarily polynomials, that generate curves with geometric properties and with algorithms similar to the Bézier curves and that expand the range of applications of the Bézier curves, thus being able to reach more complex shapes. The main results we obtain are:
- Given an initial system, a set of weights and, a positive function Phi, we define a new system of functions called weighted Phi-transformed system.
- We show that weighted Phi-transformed systems include important bases useful in CAGD and Statistics, such as Poisson basis, Bernstein basis of negative degree or rational bases.
- We prove that weighted Phi-transformed system inherits from the initial system its shape preserving properties.
- Curves defined by Bernstein bases and rational B-splines have become a standard tool in CAGD since they allow the exact representation of numerous conic, sphere, and cylinder sections. In this thesis, we obtain as an example of a weighted Phi-transformed system a general class of totally positive rational bases that belong to rational spaces that mix algebraic, trigonometric and hyperbolic polynomials. In addition, we present evaluation and subdivision algorithms for the parametric curves generated by these bases.
- We obtain as an example of the general class of rational bases previously proposed a particular class of totally positive rational bases that satisfy recurrence relations and generate new nested rational spaces. For these bases, we present evaluation and subdivision algorithms.
- Applying Artificial Intelligence techniques, we present a one-hidden-layer neural network based on the proposed general class of rational bases. With this neural network, we tackle the problem of finding the rational curves that best fit a given set of data points. In this process of approximation, the rational basis is a hyperparameter and can be changed by substituting the linear factors for polynomial, trigonometric or hyperbolic functions, thus being able to reach more difficult shapes and expanding in this way the potential range of applications of this neural network.
On the other hand, our research also focuses on the field of Numerical Linear Algebra, specifically on the design and analysis of algorithms adapted to the structure of totally positive matrices that allow us to solve with high relative accuracy algebraic problems associated with these matrices. Nowadays, many of the problems that arise in Physics, Engineering, Chemistry, Biomedicine or CAGD, among others, require numerical methods with which to solve systems of linear equations or with which to find the eigenvalues or singular values of the associated matrices to the mathematical model. These numerical methods are the object of intense research because in current applications new classes of structured matrices are continually appearing (among we can find totally positive matrices) with which the need arises to develop more efficient and/or accurate specific algorithms than the existing ones.
Obtaining the bidiagonal factorization of the totally positive matrices in terms of the multipliers of the Neville elimination has been a very important point in obtaining accurate algorithms with which to perform algebraic calculations with these matrices with a much smaller error than that of conventional algorithms and with the same computational cost. Up to now, this has been achieved with some relevant subclasses of TP matrices with applications to CAGD to Finance or to Combinatorics. In this thesis, we present the results that guarantee the good computational properties of the weighted Phi-transformed systems. Also, we show examples of Wronskian matrices for which different algebraic computations can be performed with high relative accuracy. Wronskian matrices frequently arise in different applications, for instance, in Hermite interpolation problems, and in particular in Taylor interpolation problems. However, so far, there are no examples of accurate computations for matrices involving derivatives of the basis functions. The main results we obtain are:
-From the bidiagonal factorization of the collocation matrix of an initial system we design an accurate algorithm to construct the bidiagonal factorization of the collocation matrix of the corresponding weighted Phi-transformed system. We use this algorithm to perform accurately different algebraic computations. Due to the good geometric properties of the curves generated by the weighted Phi-transformed systems, this algorithm can be useful in interpolation and approximation problems.
-We present accurate algorithms with which to calculate the bidiagonal factorization of the Wronskian matrix of the monomial basis of polynomials and the bidiagonal factorization of the Wronskian matrix of the basis of exponential polynomials. It is also shown that these algorithms can be used to perform accurately some algebraic computations associated with these Wronskian matrices, such as the computation of their inverses, their eigenvalues or their singular values, and the solutions of some linear systems.
-We obtain an accurate method to construct the bidiagonal factorization of the collocation and Wronskian matrices of the Jacobi polynomials, and we use it to compute with high relative accuracy their eigenvalues, singular values, inverse matrices and, the solution of some linear systems associated with these matrices. We also consider the particular cases of collocation and Wronskian matrices of Legendre polynomials, Gegenbauer polynomials, Chebyshev polynomials of the first and second type, and Jacobi rational polynomials.
-We design a method to obtain the bidiagonal factorization of the Wronskian matrix of the Bessel polynomials and the bidiagonal factorization of the Wronskian matrix of the Laguerre polynomials. We use this method to compute with high relative accuracy their singular values, inverse matrices, as well as the solution of some linear systems.
-We provide an algorithm to obtain the bidiagonal factorization of the Wronskian matrices of Bernstein polynomials and the bidiagonal factorization of other related bases, such as the negative degree Bernstein basis or the negative binomial basis. We also show that this algorithm can be used to perform with high relative accuracy some algebraic computations with these Wronskian matrices, such as the computation of their inverses, their eigenvalues or their singular values, and the solutions of some related linear systems.
-We design accurate algorithms with which to obtain the bidiagonal factorization of the Wronskian matrix of the geometric basis and the bidiagonal factorization of the Wronskian matrix of the Poisson basis. We use these algorithms to compute accurately different algebraic computations.
-The complexity of all the proposed algorithms for solving the mentioned algebraic problems is comparable to that of the traditional LAPACK algorithms, which, as we will illustrate, deliver no such accuracy.
This work is a doctoral thesis by compendium of publications and is structured in five parts. The first part is composed on the one hand, by the Introduction, and on the other hand, by the Background with the auxiliary results and the tools that we are going to use in the development of the work. In the second part, we present the articles that belong to the compendium of publications of this thesis. In the third part, we justify the thematic unit of the mentioned publications. We also include their main results. In the fourth part, we present the latest results that we have obtained and that are not included in the articles that belong to the compendium of publications of this thesis. Finally, in the fifth part, the conclusions and the possible future work that might continue to be developed as a result of the research of this thesis are described. The code of the algorithms and of the numerical experiments can be found and downloaded at the following website: https://github.com/BeatrizRubio.
