Pasar al contenido principal

ANALISIS DE LA REPRESENTACION DE CURVAS Y SUPERFICIES, CALCULOS PRECISOS CON MATRICES ESTRUCTURADAS Y APLICACIONES

PGC2018-096321-B-I00

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de Generación de Conocimiento y Fortalecimiento Científico y Tecnológico del Sistema de I+D+i
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D (Excelencia / Generación de Conocimiento)
Año convocatoria 2018
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSIDAD DE ZARAGOZA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 40
Encontrada(s) 1 página(s)

RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Succinct Encoding of Binary Strings Representing Triangulations

  • Fuentes Sepúlveda, José
  • Seco, Diego
  • Viaña, Raquel
Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature, [Abstract]: We consider the problem of designing a succinct data structure for representing the connectivity of planar triangulations. The main result is a new succinct encoding achieving the information-theory optimal bound of 3.24 bits per vertex, while allowing efficient navigation. Our representation is based on the bijection of Poulalhon and Schaeffer (Algorithmica, 46(3):505–527, 2006) that defines a mapping between planar triangulations and a special class of spanning trees, called PS-trees. The proposed solution differs from previous approaches in that operations in planar triangulations are reduced to operations in particular parentheses sequences encoding PS-trees. Existing methods to handle balanced parentheses sequences have to be combined and extended to operate on such specific sequences, essentially for retrieving matching elements. The new encoding supports extracting the d neighbors of a query vertex in O(d) time and testing adjacency between two vertices in O(1) time. Additionally, we provide an implementation of our proposed data structure. In the experimental evaluation, our representation reaches up to 7.35 bits per vertex, improving the space usage of state-of-the-art implementations for planar embeddings., This work was supported in part by National Agency for Research and Development (ANID)—Millennium Science Initiative Program—Code ICN17_002, and ANID—PAI under Grant 77190038, Fondecyt Postdoctoral under grant 3170534 and Basal Funds FB0001 (José Fuentes-Sepúlveda) and through Fondecyt Regular under Grant 1170497 (Diego Seco). This research has also been supported by Spanish Research Grant PGC2018-096321-B-I00 from the Spanish Ministerio de Ciencia, Innovación y Universidades. The author Raquel Viaña is a member of the Research Group asynacs (Ref.CT-CE2019/683) of Universidad de Alcalá., Chile. Agencia Nacional de Investigación y Desarrollo; ICN17_002, Chile. Agencia Nacional de Investigación y Desarrollo; 77190038, Chile. Comisión Nacional de Investigación Científica y Tecnológica; 3170534, Chile. Comisión Nacional de Investigación Científica y Tecnológica; 1170497
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Trajectory definition with high relative accuracy (HRA) by parametric representation of curves in nano-positioning systems

  • Díaz Pérez, Lucía
  • Rubio Serrano, Beatriz
  • Albajez García, José A.
  • Yagüe Fabra, José A.Y
  • Mainar Maza, Esmeralda
  • Torralba Gracia, Marta
Nanotechnology applications demand high accuracy positioning systems. Therefore, in order to achieve sub-micrometer accuracy, positioning uncertainty contributions must be minimized by implementing precision positioning control strategies. The positioning control system accuracy must be analyzed and optimized, especially when the system is required to follow a predefined trajectory. In this line of research, this work studies the contribution of the trajectory definition errors to the final positioning uncertainty of a large-range 2D nanopositioning stage. The curve trajectory is defined by curve fitting using two methods: traditional CAD/CAM systems and novel algorithms for accurate curve fitting. This novel method has an interest in computer-aided geometric design and approximation theory, and allows high relative accuracy (HRA) in the computation of the representations of parametric curves while minimizing the numerical errors. It is verified that the HRA method offers better positioning accuracy than commonly used CAD/CAM methods when defining a trajectory by curve fitting: When fitting a curve by interpolation with the HRA method, fewer data points are required to achieve the precision requirements. Similarly, when fitting a curve by a least-squares approximation, for the same set of given data points, the HRA method is capable of obtaining an accurate approximation curve with fewer control points.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Geometric properties and algorithms for rational q-Bézier curves and surfaces

  • Delgado, Jorge
  • Peña, J.M.
In this paper, properties and algorithms of q-Bézier curves and surfaces are analyzed. It is proven that the only q-Bézier and rational q-Bézier curves satisfying the boundary tangent property are the Bézier and rational Bézier curves, respectively. Evaluation algorithms formed by steps in barycentric form for rational q-Bézier curves and surfaces are provided.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Neural-network-based curve fitting using totally positive rational bases

  • Gonzalez-Diaz, R.
  • Mainar, E.
  • Paluzo-Hidalgo, E.
  • Rubio, B.
This paper proposes a method for learning the process of curve fitting through a general class of totally positive rational bases. The approximation is achieved by finding suitable weights and control points to fit the given set of data points using a neural network and a training algorithm, called AdaMax algorithm, which is a first-order gradient-based stochastic optimization. The neural network presented in this paper is novel and based on a recent generalization of rational curves which inherit geometric properties and algorithms of the traditional rational Bézier curves. The neural network has been applied to different kinds of datasets and it has been compared with the traditional least-squares method to test its performance. The obtained results show that our method can generate a satisfactory approximation.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Compensated evaluation of tensor product surfaces in CAGD

  • Delgado Gracia, J.
In computer-aided geometric design, a polynomial surface is usually represented in Bézier form. The usual form of evaluating such a surface is by using an extension of the de Casteljau algorithm. Using error-free transformations, a compensated version of this algorithm is presented, which improves the usual algorithm in terms of accuracy. A forward error analysis illustrating this fact is developed.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Almost strictly sign regular rectangular matrices

  • Alonso, P.
  • Peña, J.M.
  • Serrano, M.L.
Almost strictly sign regular matrices are sign regular matrices with a special zero pattern and whose nontrivial minors are nonzero. In this paper we provide several properties of almost strictly sign regular rectangular matrices of maximal rank and analyze their QR factorization.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Inverse central ordering for the Newton interpolation formula

  • Carnicer, J. M.
  • Khiar, Y.
  • Peña, J. M.
An inverse central ordering of the nodes is proposed for the Newton interpolation formula. This ordering may improve the stability for certain distributions of nodes. For equidistant nodes, an upper bound of the conditioning is provided. This bound is close to the bound of the conditioning in the Lagrange interpolation formula, whose conditioning is the lowest. This ordering is related to a pivoting strategy of a matrix elimination procedure called Neville elimination. The results are illustrated with examples.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Accurate computations with Wronskian matrices of Bessel and Laguerre polynomials

  • Mainar, E.
  • Peña, J.M.
  • Rubio, B.
This paper provides an accurate method to obtain the bidiagonal factorization of Wronskian matrices of Bessel polynomials and of Laguerre polynomials. This method can be used to compute with high relative accuracy their singular values, the inverse of these matrices, as well as the solution of some related systems of linear equations. Numerical examples illustrating the theoretical results are included. © 2022 The Authors
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Depth of almost strictly sign regular matrices

  • Alonso, Pedro
  • Jiménez, Jorge
  • Peña, Juan Manuel
  • Serrano, María Luisa
The concept of depth of an almost strictly sign regular matrix is introduced and used to simplify some algorithmic characterizations of these matrices.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Total positivity and accurate computations with Gram matrices of Bernstein bases

  • Mainar, E.
  • Peña, J. M.
  • Rubio, B.
In this paper, an accurate method to construct the bidiagonal factorization of Gram (mass) matrices of Bernstein bases of positive and negative degree is obtained and used to compute with high relative accuracy their eigenvalues, singular values and inverses. Numerical examples are included.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Accurate computations with matrices related to bases {tie¿t}

  • Mainar, E.
  • Peña, J. M.
  • Rubio, B.
The total positivity of collocation, Wronskian and Gram matrices corresponding to bases of the form (eλt,teλt,…,tneλt) is analyzed. A bidiagonal decomposition providing the accurate numerical resolution of algebraic linear problems with these matrices is derived. The numerical experimentation confirms the accuracy of the proposed methods.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Accurate and efficient computations with Wronskian matrices of Bernstein and related bases

  • Mainar, Esmeralda
  • Peña, Juan M.
  • Rubio, Beatriz
In this article, we provide a bidiagonal decomposition of the Wronskian matrices of Bernstein bases of polynomials and other related bases such as the Bernstein basis of negative degree or the negative binomial basis. The mentioned bidiagonal decompositions are used to achieve algebraic computations with high relative accuracy for these Wronskian matrices. The numerical experiments illustrate the accuracy obtained using the proposed decomposition when computing inverse matrices, eigenvalues or singular values, and the solution of some related linear systems. © 2021 John Wiley & Sons Ltd.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Accurate computations with Wronskian matrices

  • Mainar, E.
  • Peña, J.M.
  • Rubio, B.
In this paper we provide algorithms for computing the bidiagonal decomposition of the Wronskian matrices of the monomial basis of polynomials and of the basis of exponential polynomials. It is also shown that these algorithms can be used to perform accurately some algebraic computations with these Wronskian matrices, such as the calculation of their inverses, their eigenvalues or their singular values and the solutions of some linear systems. Numerical experiments illustrate the results.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Spherical Bessel functions and critical lengths

  • Carnicer, J. M.
  • Mainar, E.
  • Peña, J. M.
The critical length of a space of functions can be described as the supremum of the length of the intervals where Hermite interpolation problems are unisolvent for any choice of nodes. We analyze the critical length for spaces containing products of algebraic polynomials and trigonometric functions. We show the relation of these spaces with spherical Bessel functions and bound above their critical length by the first positive zero of a Bessel function of the first kind.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Bidiagonal decompositions of Vandermonde-type matrices of arbitrary rank

  • Delgado, Jorge
  • Koev, Plamen
  • Marco, Ana
  • Martínez, José-Javier
  • Peña, Juan Manuel
  • Persson, Per-Olof
  • Spasov, Steven
We present a method to derive new explicit expressions for bidiagonal decompositions of Vandermonde and related matrices such as the (-, -) Bernstein-Vandermonde ones, among others. These results generalize the existing expressions for nonsingular matrices to matrices of arbitrary rank. For totally nonnegative matrices of the above classes, the new decompositions can be computed efficiently and to high relative accuracy componentwise in floating point arithmetic. In turn, matrix computations (e.g., eigenvalue computation) can also be performed efficiently and to high relative accuracy.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Gaussian Markov Random fields and totally positive matrices

  • Baz, Juan
  • Alonso, Pedro
  • Peña, Juan Manuel
  • Pérez-Fernández, Raúl
The present paper focuses on the study of the conditions under which the covariance matrix of a multivariate Gaussian distribution is totally positive, paying particular attention to multivariate Gaussian distributions that are Gaussian Markov Random Fields. More specifically, it is proven that, if the graph over which the Gaussian Markov Random Field is defined consists of path graphs and the covariances between adjacent variables on the graph are non-negative, then there always exists a reordering of the variables that renders the resulting covariance matrix totally positive. Moreover, this reordering is identified and some cases for which the conditions for the covariance matrix of a multivariate Gaussian distribution to be totally positive are necessary and sufficient are provided.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Accurate and fast computations with Green matrices

  • Delgado, Jorge
  • Peña, Guillermo
  • Peña, Juan Manuel
This paper provides a linear time complexity method to obtain the bidiagonal decomposition of Green matrices with high relative accuracy. In addition, when the Green matrix is nonsingular and totally positive, this bidiagonal decomposition can be used to compute the eigenvalues, the inverse and the solution of some linear system of equations with high relative accuracy. A numerical example illustrates the advantages of this method.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

A new class of trigonometric B-Spline Curves

  • Albrecht, Gudrun
  • Mainar, Esmeralda
  • Peña, Juan Manuel
  • Rubio, Beatriz
We construct one-frequency trigonometric spline curves with a de Boor-like algorithm for evaluation and analyze their shape-preserving properties. The convergence to quadratic B-spline curves is also analyzed. A fundamental tool is the concept of the normalized B-basis, which has optimal shape-preserving properties and good symmetric properties.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Green Matrices, Minors and Hadamard Products

  • Delgado, Jorge
  • Peña, Guillermo
  • Peña, Juan Manuel
Green matrices are interpreted as discrete version of Green functions and are used when working with inhomogeneous linear system of differential equations. This paper discusses accurate algebraic computations using a recent procedure to achieve an important factorization of these matrices with high relative accuracy and using alternative accurate methods. An algorithm to compute any minor of a Green matrix with high relative accuracy is also presented. The bidiagonal decomposition of the Hadamard product of Green matrices is obtained. Illustrative numerical examples are included.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Total positivity and accurate computations with Gram matrices of Said-Ball bases

  • Mainar, E.
  • Peña, J.M.
  • Rubio, B.
In this article, it is proved that Gram matrices of totally positive bases of the space of polynomials of a given degree on a compact interval are totally positive. Conditions to guarantee computations to high relative accuracy with those matrices are also obtained. Furthermore, a fast and accurate algorithm to compute the bidiagonal factorization of Gram matrices of the Said-Ball bases is obtained and used to compute to high relative accuracy their singular values and inverses, as well as the solution of some linear systems associated with these matrices. Numerical examples are included.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Polynomial Total Positivity and High Relative Accuracy Through Schur Polynomials

  • Díaz, P.
  • Mainar, E.
  • Rubio, B.
In this paper, Schur polynomials are used to provide a bidiagonal decomposition of polynomial collocation matrices. The symmetry of Schur polynomials is exploited to analyze the total positivity on some unbounded intervals of a relevant class of polynomial bases. The proposed factorization is used to achieve relative errors of the order of the unit round-off when solving algebraic problems involving the collocation matrix of relevant polynomial bases, such as the Hermite basis. The numerical experimentation illustrates the accurate results obtained when using the findings of the paper.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

On the stability of the representation of finite rank operators

  • Carnicer, J.M.
  • Mainar, E.
  • Peña, J.M.
The stability of the representation of finite rank operators in terms of a basis is analyzed. A conditioning is introduced as a measure of the stability properties. This conditioning improves some other conditionings because it is closer to the Lebesgue function. Improved bounds for the conditioning of the Fourier sums with respect to an orthogonal basis are obtained, in particular, for Legendre, Chebyshev, and disk polynomials. The Lagrange and Newton formulae for the interpolating polynomial are also considered.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

High relative accuracy through Newton bases

  • Mainar, E.
  • Peña, J.M.
  • Rubio, B.
Bidiagonal factorizations for the change of basis matrices between monomial and Newton polynomial bases are obtained. The total positivity of these matrices is characterized in terms of the sign of the nodes of the Newton bases. It is shown that computations to high relative accuracy for algebraic problems related to these matrices can be achieved whenever the nodes have the same sign. Stirling matrices can be considered particular cases of these matrices, and then computations to high relative accuracy for collocation and Wronskian matrices of Touchard polynomial bases can be obtained. The performed numerical experimentation confirms the accurate solutions obtained when solving algebraic problems using the proposed factorizations, for instance, for the calculation of their eigenvalues, singular values, and inverses, as well as the solution of some linear systems of equations associated with these matrices.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

A Shape Preserving Class of Two-Frequency Trigonometric B-Spline Curves

  • Albrecht, Gudrun
  • Mainar, Esmeralda
  • Peña, Juan Manuel
  • Rubio, Beatriz
This paper proposes a new approach to define two frequency trigonometric spline curves with interesting shape preserving properties. This construction requires the normalized B-basis of the space U4(Iα)=span{1,cost,sint,cos2t,sin2t} defined on compact intervals Iα=[0,α], where α is a global shape parameter. It will be shown that the normalized B-basis can be regarded as the equivalent in the trigonometric space U4(Iα) to the Bernstein polynomial basis and shares its well-known symmetry properties. In fact, the normalized B-basis functions converge to the Bernstein polynomials as α→0. As a consequence, the convergence of the obtained piecewise trigonometric curves to uniform quartic B-Spline curves will be also shown. The proposed trigonometric spline curves can be used for CAM design, trajectory-generation, data fitting on the sphere and even to define new algebraic-trigonometric Pythagorean-Hodograph curves and their piecewise counterparts allowing the resolution of C(3 Hermite interpolation problems.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

An evaluation algorithm for q-Bézier triangular patches formed by convex combinations

  • Delgado, J.
  • Orera, H.
  • Peña, J.M.
An extension to triangular domains of the univariate q-Bernstein basis functions is introduced and analysed. Some recurrence relations and properties such as partition of unity and degree elevation are proved for them. It is also proved that they form a basis for the space of polynomials of total degree less than or equal to n on a triangle. In addition, it is presented a de Casteljau type evaluation algorithm whose steps are all linear convex combinations.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Accurate bidiagonal decomposition of collocation matrices of weighted ¿-transformed systems

  • Mainar, Esmeralda
  • Peña, Juan Manuel
  • Rubio, Beatriz
Given a system of functions, we introduce the concept of weighted f-transformed system, which will include a very large class of useful representations in Statistics and Computer Aided Geometric Design. An accurate bidiagonal decomposition of the collocation matrices of these systems is obtained. This decomposition is used to present computational methods with high relative accuracy for solving algebraic problems with collocation matrices of weighted f-transformed systems such as the computation of eigenvalues, singular values, and the solution of some linear systems. Numerical examples illustrate the accuracy of the performed computations.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Stabilized recovery and model reduction for multivariate exponential polynomials

  • Peña, Juan Manuel
  • Sauer, Tomas
Recovery of multivariate exponential polynomials, i.e., the multivariate version of Prony's problem, can be stabilized by using more than the minimally needed multiinteger samples of the function. We present an algorithm that takes into account this extra information and prove a backward error estimate for the algebraic recovery method SMILE. In addition, we give a method to approximate data by an exponential polynomial sequence of a given structure as a step in the direction of multivariate model reduction.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Accurate Algorithms for Bessel Matrices

  • Delgado, Jorge
  • Orera, Héctor
  • Peña, J.M.
In this paper, we prove that any collocation matrix of Bessel polynomials at positive points is strictly totally positive, that is, all its minors are positive. Moreover, an accurate method to construct the bidiagonal factorization of these matrices is obtained and used to compute with high relative accuracy the eigenvalues, singular values and inverses. Similar results for the collocation matrices for the reverse Bessel polynomials are also obtained. Numerical examples illustrating the theoretical results are included. © 2019, Springer Science+Business Media, LLC, part of Springer Nature.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Accurate bidiagonal decomposition and computations with generalized Pascal matrices

  • Delgado, J.
  • Orera, H.
  • Peña, J.M.
This paper provides an accurate method to obtain the bidiagonal factorization of many generalized Pascal matrices, which in turn can be used to compute with high relative accuracy the eigenvalues, singular values and inverses of these matrices. Numerical examples are included.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Optimal properties of tensor product of B-bases

  • Delgado Gracia, J
  • Orera, H
  • Peña Ferrández, JM
It is proved the optimal conditioning for the infinity-norm of collocation matrices of the tensor product of normalized B-bases among the tensor product of all normalized totally positive bases of the corresponding space of functions. Bounds for the minimal eigenvalue and singular value and illustrative numerical examples are also included. (C) 2021 Elsevier Ltd. All rights reserved.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

High relative accuracy with matrices of q-integers

  • Delgado J.
  • Orera H.
  • Peña J.M.
This article shows that the bidiagonal decomposition of many important matrices of q-integers can be constructed to high relative accuracy (HRA). This fact can be used to compute with HRA the eigenvalues, singular values, and inverses of these matrices. These results can be applied to collocation matrices of q-Laguerre polynomials, q-Pascal matrices, and matrices formed by q-Stirling numbers. Numerical examples illustrate the theoretical results. © 2021 John Wiley & Sons Ltd.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Error bounds for linear complementarity problems of BpR -matrices

  • Orera, H.
  • Peña, J.M.
It is proved that any BpR-matrix has positive determinant. For p> 0 , norm bounds for the inverses of BpR-matrices and error bounds for linear complementarity problems associated with BpR-matrices are provided. In this last case, the bounds are simpler than previous bounds and also have the advantage that they can be used without previously knowing whether we have a BpR-matrix. Some numerical examples show that these new bounds can be considerably sharper than previous ones.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Radon’s construction and matrix relations generating syzygies

  • Carnicer, J. M.
  • Godés, C.
  • Sauer, T.
Let ¿n be the set of bivariate polynomials of degree not greater than n. A ¿n-correct set of nodes is a set such that the Lagrange interpolation problem with respect to these nodes has a unique solution. A maximal line of a ¿n-correct set is any line containing exactly n+ 1 nodes. Syzygy matrices can be used to find linear factors of the fundamental polynomials and detect maximal lines. We suggest to use matrix relations in order to generate syzygies, identify linear factors of fundamental polynomials and detect maximal lines. We interpret our results in the important case of GC sets trying to shed some light on the Gasca-Maeztu conjecture.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Characterizations and accurate computations for tridiagonal Toeplitz matrices

  • Delgado, J.
  • Orera, H.
  • Peña, J.M.
Tridiagonal Toeplitz P-matrices, M-matrices and totally positive matrices are characterized. For some classes of tridiagonal matrices and tridiagonal Toeplitz matrices, it is shown that many algebraic computations can be performed with high relative accuracy.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

High relative accuracy with some special matrices related to G and ß functions

  • Delgado, Jorge
  • Peña, Juan Manuel
For some families of totally positive matrices using Γ and functions, we provide their bidiagonal factorization. Moreover, when these functions are define dover integers, we prove that the bidiagonal factorization can be computed with high relative accuracy and so we can compute with high relative accuracy their eigenvalues,singular values,inverses and the solutions of some associated linear systems. We provide numerical examples illustrating this high relative accuracy.
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Succinct Encoding of Binary Strings Representing Triangulations

  • Fuentes Sepúlveda, José
  • Seco, Diego
  • Viaña Fernández, Raquel|||0000-0001-5484-9104
We consider the problem of designing a succinct data structure for representing the connectivity of planar triangulations. The main result is a new succinct encoding achieving the information-theory optimal bound of 3.24 bits per vertex, while allowing efficient navigation. Our representation is based on the bijection of Poulalhon and Schaeffer (Algorithmica, 46(3):505-527, 2006) that defines a mapping between planar triangulations and a special class of spanning trees, called PS-trees. The proposed solution differs from previous approaches in that operations in planar triangulations are reduced to operations in particular parentheses sequences encoding PS-trees. Existing methods to handle balanced parentheses sequences have to be combined and extended to operate on such specific sequences, essentially for retrieving matching elements. The new encoding supports extracting the d neighbors of a query vertex in O(d) time and testing adjacency between two vertices in O(1) time. Additionally, we provide an implementation of our proposed data structure. In the experimental evaluation, our representation reaches up to 7.35 bits per vertex, improving the space usage of state-of-the-art implementations for planar embeddings., Ministerio de Ciencia, Innovación y Universidades
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Accurate computations with collocation matrices of the Lupaş-type (p,q)-analogue of the Bernstein basis

  • Marco García, Ana|||0000-0003-4662-6327
  • Martínez Fernández de las Heras, José Javier|||0000-0002-8322-0361
  • Viaña Fernández, Raquel|||0000-0001-5484-9104
A fast and accurate algorithm to compute the bidiagonal decomposition of collocation matrices of the Lupaş-type (p,q)-analogue of the Bernstein basis is presented. The error analysis of the algorithm and the perturbation theory for the bidiagonal decomposition are also included. Starting from this bidiagonal decomposition, the accurate and efficient solution of several linear algebra problems involving these matrices is addressed: linear system solving, eigenvalue and singular value computation, and computation of the inverse and the Moore-Penrose inverse. The numerical experiments carried out show the good behaviour of the algorithm., Agencia Estatal de Investigación
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Error analysis, perturbation theory and applications of the bidiagonal decomposition of rectangular totally-positive h-Bernstein-Vandermonde matrices

  • Marco García, Ana|||0000-0003-4662-6327
  • Martínez Fernández de las Heras, José Javier|||0000-0002-8322-0361
  • Viaña Fernández, Raquel|||0000-0001-5484-9104
A fast and accurate algorithm to compute the bidiagonal decomposition of rectangular totally positive h-Bernstein-Vandermonde matrices is presented. The error analysis of the algorithm and the perturbation theory for the bidiagonal decomposition of totally positive h-Bernstein-Vandermonde matrices are addressed. The computation of this bidiagonal decomposition is used as the first step for the accurate and efficient computation of the singular values of rectangular totally positive h-Bernstein-Vandermonde matrices and for solving least squares problems whose coefficient matrices are such matrices., Agencia Estatal de Investigación
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Bidiagonal decompositions of Vandermonde-type matrices of arbitrary rank

  • Delgado, Jorge
  • Koev, Plamen
  • Marco García, Ana|||0000-0003-4662-6327
  • Martínez Fernández de las Heras, José Javier|||0000-0002-8322-0361
  • Peña Ferrández, Juan Manuel
  • Persson, Per-Oloff
  • Spasov, Steven
We present a method to derive new explicit expressions for bidiagonal decompositions of Vandermonde and related matrices such as the (q-, h-) Bernstein-Vandermonde ones, among others. These results generalize the existing expressions for nonsingular matrices to matrices of arbitrary rank. For totally nonnegative matrices of the above classes, the new decompositions can be computed efficiently and to high relative accuracy componentwise in floating point arithmetic. In turn, matrix computations (e.g., eigenvalue computation) can also be performed efficiently and to high relative accuracy., Agencia Estatal de Investigación, Gobierno de Aragón
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Accurate computations with totally positive matrices applied to the computation of Gaussian quadrature formulae

  • Marco García, Ana|||0000-0003-4662-6327
  • Martínez Fernández de las Heras, José Javier|||0000-0002-8322-0361
  • Viaña Fernández, Raquel|||0000-0001-5484-9104
For some families of classical orthogonal polynomials defined on appropriate intervals, it is shown that the corresponding Jacobi matrices are totally positive and their bidiagonal factorizations can be accurately computed. By exploiting these facts, an algorithm to compute with high relative accuracy the eigenvalues of those Jacobi matrices, and consequently the nodes of Gaussian quadrature formulae for those families of orthogonal polynomials, is presented. An algorithm is also presented for the computation of the eigenvectors of these Jacobi matrices, and hence the weights of Gaussian quadrature formulae. Although in this case high relative accuracy is not theoretically guaranteed, the numerical experiments with our algorithm provide very accurate results., Agencia Estatal de Investigación