Skip to main content

Resultados relacionados

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

Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication 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
Publication 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
Publication 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
Publication 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
Publication 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
Publication 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
Publication 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
Publication 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
Publication Artículo científico (JournalArticle)

Total positivity and high relative accuracy for several classes of Hankel matrices

  • Mainar, E.
  • Peña, J. M.
  • Rubio, B.
Gramian matrices with respect to inner products defined for Hilbert spaces supported on bounded and unbounded intervals are represented through a bidiagonal factorization. It is proved that the considered matrices are strictly totally positive Hankel matrices and their catalecticant determinants are also calculated. Using the proposed representation, the numerical resolution of linear algebra problems with these matrices can be achieved to high relative accuracy. Numerical experiments are provided, and they illustrate the excellent results obtained when applying the theoretical results.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

High relative accuracy for rational q-Bernstein–Vandermonde matrices

  • Delgado, Jorge
  • Orera, Héctor
  • Peña, J.M.
In this article, an accurate and efficient method to compute the eigenvalues, singular values and inverses of nonsingular totally positive rational q-Bernstein–Vandermonde matrices and the solution of some associated linear systems of equations is provided. The method is based on the representation of a totally positive matrix in terms of its bidiagonal decomposition and the use of a library of accurate functions designed for this class of matrices. © 2024 Informa UK Limited, trading as Taylor & Francis Group.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Accurate computations with block checkerboard pattern matrices

  • Delgado, Jorge
  • Orera, Héctor
  • Peña, J. M.
In this work, block checkerboard sign pattern matrices are introduced and analyzed. They satisfy the generalized Perron–Frobenius theorem. We study the case related to total positive matrices in order to guarantee bidiagonal decompositions and some linear algebra computations with high relative accuracy. A result on intervals of checkerboard matrices is included. Some numerical examples illustrate the theoretical results.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Bidiagonal Factorizations of Filbert and Lilbert Matrices

  • Khiar, Yasmina
  • Mainar, Esmeralda
  • Peña, Juan Manuel
  • Royo-Amondarain, Eduardo
  • Rubio, Beatriz
Extensions of Filbert and Lilbert matrices are addressed in this work. They are reciprocal Hankel matrices based on Fibonacci and Lucas numbers, respectively, and both are related to Hilbert matrices. The Neville elimination is applied to provide explicit expressions for their bidiagonal factorization. As a byproduct, formulae for the determinants of these matrices are obtained. Finally, numerical experiments show that several algebraic problems involving these matrices can be solved with outstanding accuracy, in contrast with traditional approaches.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

An Optimal Property of B-Bases for the Modified Richardson Method

  • Peña, Juan Manuel
A space with a normalized totally positive basis has a unique normalized B-basis. In computer-aided geometric design, normalized B-bases present optimal shape-preserving properties. More optimal properties of normalized B-bases were proved previously. This paper provides a new optimal property concerning the modified Richardson iterative method when applied to collocation matrices of normalized B-bases. Moreover, a similar optimal property is proved for the tensor product of normalized B-bases.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Optimal properties related to Total Positivity and Wronskian matrices

  • Peña, J. M.
B-bases are totally positive bases satisfying several optimal properties. In this paper we prove a new optimal property of B-bases related to the conditioning of their Wronskian matrices.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Balancing the cardinality of clusters with a distance constraint: a fast algorithm

  • Calvete, Herminia I.
  • Galé, Carmen
  • Iranzo, José A.
Logistics companies partition the customers they serve into delivery zones as a tactical decision and manage the customers assigned to each zone as a cluster for the purpose of routing, workload allocation, etc. Frequently, this partition is made in accordance with customers’ geographical location, which can result in very unbalanced clusters in terms of the number of customers they include. In addition, in the day-to-day operations, not necessarily all customers need to be served every day so, even if the clusters originally created are balanced, daily needs may lead to unbalanced clusters. Given an a priori assignment of customers to clusters, improving the balance between clusters in advance of workload management is therefore a key issue. This paper addresses the problem of balancing clusters, when there is a distance constraint that prevents reassigning customers to clusters far away from their original pre-assignment. This problem is formulated as a lexicographic biobjective optimization model. The highest priority objective function minimizes the variance of the number of customers in the clusters. The second ranked objective function minimizes the total distance resulting from all reassignments. A fast and effective heuristic algorithm is developed, based on exploring customer reassignments, either by comparing clusters two by two or by extending the search to allow for sequential customer swaps among clusters. Both the quality of the solution and the computational time required encourage the use of this algorithm by logistics companies to balance clusters in real scenarios.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

On the accurate computation of the Newton form of the Lagrange interpolant

  • Khiar, Y.
  • Mainar, E.
  • Royo-Amondarain, E.
  • Rubio, B.
In recent years many efforts have been devoted to finding bidiagonal factorizations of nonsingular totally positive matrices, since their accurate computation allows to numerically solve several important algebraic problems with great precision, even for large ill-conditioned matrices. In this framework, the present work provides the factorization of the collocation matrices of Newton bases—of relevance when considering the Lagrange interpolation problem—together with an algorithm that allows to numerically compute it to high relative accuracy. This further allows to determine the coefficients of the interpolating polynomial and to compute the singular values and the inverse of the collocation matrix. Conditions that guarantee high relative accuracy for these methods and, in the former case, for the classical recursion formula of divided differences, are determined. Numerical errors due to imprecise computer arithmetic or perturbed input data in the computation of the factorization are analyzed. Finally, numerical experiments illustrate the accuracy and effectiveness of the proposed methods with several algebraic problems, in stark contrast with traditional approaches.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Approximate analytical solutions of the homologous collapse’s radial evolution in time

  • Calvo, Manuel
  • Elipe, Antonio
  • Rández, Luis
The homologous collapse of a uniform density sphere under its self-gravity is a well-known model in cosmological studies. In the analytical integration, the evolution of the radius of the sphere is defined in terms of a parameter that is related to the physical time through a transcendental equation. The aim of this note is to construct new approximate solutions of this transcendental equation. After close examination of the piecewise Padé approximation introduced in a recent paper by Zhou and collaborators, several modifications that improve the accuracy of this approximation with the same computational cost are proposed. This new approximation shows that the use of piecewise Hermite interpolation leads to approximate solutions with continuity and much higher accuracy than Padé interpolants. Numerical experiments that confirm the above results are also presented.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Accurate bidiagonal decompositions of Cauchy–Vandermonde matrices of any rank

  • Delgado, Jorge
  • Koev, Plamen
  • Marco, Ana
  • Martínez, José-Javier
  • Peña, Juan Manuel
  • Persson, Per-Olof
  • Spasov, Steven
We present a new decomposition of a Cauchy–Vandermonde matrix as a product of bidiagonal matrices which, unlike its existing bidiagonal decompositions, is now valid for a matrix of any rank. The new decompositions are insusceptible to the phenomenon known as subtractive cancellation in floating point arithmetic and are thus computable to high relative accuracy. In turn, other accurate matrix computations are also possible with these matrices, such as eigenvalue computation amongst others.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Accurate Computations with Generalized Green Matrices

  • Delgado, Jorge
  • Peña, Guillermo
  • Peña, Juan Manuel
We consider generalized Green matrices that, in contrast to Green matrices, are not necessarily symmetric. In spite of the loss of symmetry, we show that they can preserve some nice properties of Green matrices. In particular, they admit a bidiagonal decomposition. Moreover, for convenient parameters, the bidiagonal decomposition can be obtained efficiently and with high relative accuracy and it can also be used to compute all eigenvalues, all singular values, the inverse, and the solution of some linear system of equations with high relative accuracy. Numerical examples illustrate the high accuracy of the performed computations using the bidiagonal decompositions. Finally, nonsingular and totally positive generalized Green matrices are characterized.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Total Positivity and Accurate Computations Related to q-Abel Polynomials

  • Khiar, Y.
  • Mainar, E.
  • Royo-Amondarain, E.
  • Rubio, B.
The attainment of accurate numerical solutions of ill-conditioned linear algebraic problems involving totally positive matrices has been gathering considerable attention among researchers over the last years. In parallel, the interest of q-calculus has been steadily growing in the literature. In this work the q-analogue of the Abel polynomial basis is studied. The total positivity of the matrix of change of basis between monomial and q-Abel bases is characterized, providing its bidiagonal factorization. Moreover, well-known high relative accuracy results of Vandermonde matrices corresponding to increasing positive nodes are extended to the decreasing negative case. This further allows to solve with high relative accuracy several algebraic problems concerning collocation, Wronskian and Gramian matrices of q-Abel polynomials. Finally, a series of numerical tests support the presented theoretical results and illustrate the goodness of the method where standard approaches fail to deliver accurate solutions.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Totally positive Wronskian matrices and symmetric functions

  • Díaz, Pablo
  • Mainar, Esmeralda
  • Rubio, Beatriz
The elements of the bidiagonal decomposition (BD) of a totally positive (TP) collocation matrix can be expressed in terms of symmetric functions of the nodes. Making use of this result, and studying the relation between Wronskian and collocation matrices of a given TP basis of functions, we can express the entries of the BD of Wronskian matrices as the values of certain symmetric functions evaluated at a single node. Moreover, in the case of polynomial bases, we obtain compact formulae for the entries of the BD of their Wronskian matrices. Interesting examples illustrate the applications of the obtained formulae.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

The High Relative Accuracy of Computations with Laplacian Matrices

  • Orera, Héctor
  • Peña, Juan Manuel
This paper provides an efficient method to compute an LDU decomposition of the Laplacian matrix of a connected graph with high relative accuracy. Several applications of this method are presented. In particular, it can be applied to efficiently compute the eigenvalues of the mentioned Laplacian matrix. Moreover, the method can be extended to graphs with weighted edges.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

A Bilevel Approach to the Facility Location Problem with Customer Preferences Under a Mill Pricing Policy

  • Calvete, Herminia I.
  • Galé, Carmen
  • Hernández, Aitor
  • Iranzo, José A.
This paper addresses the facility location problem under a mill pricing policy, integrating customers’ behavior through the concept of preferences. The problem is modeled as a bilevel optimization problem, where the existence of ties in customers’ preferences can lead to an ill-posed bilevel problem due to the possible existence of multiple optima to the lower-level problem. As the commonly employed optimistic and pessimistic strategies are inadequate for this problem, a specific approach is proposed bearing in mind the customers’ rational behavior. In this work, we propose a novel formulation of the problem as a bilevel model in which each customer faces a lexicographic biobjective problem in which the preference is maximized and the total cost of accessing the selected facility is minimized. This allows for a more accurate representation of customer preferences and the resulting decisions regarding facility location and pricing. To address the complexities of this model, we apply duality theory to the lower-level problems and, ultimately, reformulate the bilevel problem as a single-level mixed-integer optimization problem. This reformulation incorporates big-M constants, for which we provide valid bounds to ensure computational tractability and solution quality. The computational study conducted allows us to assess, on the one hand, the effectiveness of the proposed reformulation to address the bilevel model and, on the other hand, the impact of the length of the customer preference lists and fixed opening cost for facilities on the computational time and the optimal solution.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

High Relative Accuracy With Collocation Matrices of q-Jacobi Polynomials

  • Delgado, Jorge
  • Orera, Héctor
  • Peña, Juan Manuel
Little ‐Jacobi polynomials belong to the field of quantum calculus. This article obtains the bidiagonal decomposition of the collocation matrices of these polynomials, showing that, in many cases, it can be constructed to high relative accuracy (HRA). Then, it can be used to compute with HRA the inverses, eigenvalues, and singular values of these matrices. Numerical experiments are provided and illustrate the excellent results obtained when applying the presented methods.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Accurate Computations with Generalized Pascal k-Eliminated Functional Matrices

  • Delgado, Jorge
  • Orera, Héctor
  • Peña, Juan Manuel
This paper presents an accurate method to obtain the bidiagonal decomposition of some generalized Pascal matrices, including Pascal k-eliminated functional matrices and Pascal symmetric functional matrices. Sufficient conditions to assure that these matrices are either totally positive or inverse of totally positive matrices are provided. In these cases, the presented method can be used to compute their eigenvalues, singular values and inverses with high relative accuracy. Numerical examples illustrate the high accuracy of our approach.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Estimation of the covariance matrix of a Gaussian Markov Random Field under a total positivity constraint

  • Baz, Juan
  • Alonso, Pedro
  • Peña, Juan Manuel
  • Pérez-Fernández, Raúl
Gaussian Markov Random Fields are a popular statistical model that has been used successfully in many fields of application. Recent work has studied conditions under which the covariance matrix of a Gaussian Markov Random Field over a graph of paths is totally positive. In such case, many linear algebra operations concerning the covariance matrix can be performed with High Relative Accuracy (the relative error is of order of machine precision). Unfortunately, classical estimators of the covariance matrix do not necessarily yield a totally positive matrix, even when the population covariance matrix is totally positive. Essentially, this inconvenience prevents the available High Relative Accuracy methods to be used with real-life data. Here, we present a method for the estimation of the covariance matrix of a Gaussian Markov Random Field over a graph of paths assuring the estimated covariance matrix (or its inverse) is totally positive.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

High relative accuracy for a Newton form of bivariate interpolation problems

  • Khiar, Yasmina
  • Mainar, Esmeralda
  • Royo-Amondarain, Eduardo
  • Rubio, Beatriz
The problem of bivariate polynomial interpolation using Newton-type bases is examined, leading to the application of a generalized Kronecker matrix product. Algorithms for computing the coefficients of the interpolating polynomial are presented, along with conditions that ensure relative errors of the order of machine precision. A generalization of the classical recursion formula of divided differences in two dimensions is proposed for grids that generalize the standard rectangular layout. Numerical experiments demonstrate the high accuracy achieved by the proposed approach.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

High-relative-accuracy computations with Kac-Murdock-Szegö matrices and their generalizations

  • Delgado, Jorge
  • Peña, J. M.
A linear-time-complexity method to obtain the bidiagonal decomposition of a generalized Kac-Murdock-Szegö matrix is presented. For convenient values of the parameters, it can be obtained with high relative accuracy and it can be also used to compute all eigenvalues, all singular values, the inverse and the solution of some linear systems of equations with high relative accuracy.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Total positivity, Gramian matrices, and Schur polynomials

  • Díaz, Pablo
  • Mainar, Esmeralda
  • Rubio, Beatriz
This paper investigated the total positivity of Gramian matrices associated with general bases of functions. It demonstrated that the total positivity of collocation matrices for totally positive bases extends to their Gramian matrices. Additionally, a bidiagonal decomposition of these Gramian matrices, derived from integrals of symmetric functions, was presented. This decomposition enables the design of algorithms with high relative accuracy for solving linear algebra problems involving totally positive Gramian matrices. For polynomial bases, compact and explicit formulas for the bidiagonal decomposition were provided, involving integrals of Schur polynomials. These integrals, known as Selberg-like integrals, arise naturally in various contexts within Physics and Mathematics
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

High Relative Accuracy for Corner Cutting Algorithms

  • Ballarín, Jorge
  • Delgado, Jorge
  • Peña, Juan Manuel
Corner cutting algorithms are important in computer-aided geometric design and they are associated to stochastic non-singular totally positive matrices. Non-singular totally positive matrices admit a bidiagonal decomposition. For many important examples, this factorization can be obtained with high relative accuracy. From this factorization, a corner cutting algorithm can be obtained with high relative accuracy. Illustrative examples are included.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Eigenvalue Localization for Symmetric Positive Toeplitz Matrices

  • Peña, Juan M.
Given a real symmetric matrix, several inclusion and exclusion intervals containing its eigenvalues can be given. In this paper, for symmetric positive Toeplitz matrices, we provide an inclusion interval and, under an additional hypothesis, we also give two disjoint intervals contained in the previous one and containing all the eigenvalues. Examples are included, showing that these two intervals are necessary and that they can provide precise information on the localization of the eigenvalues. Sufficient conditions for positive definiteness are included. Necessary and sufficient conditions for the total positivity of symmetric positive Toeplitz matrices are presented. A characterization of symmetric totally positive circulant matrices is also obtained.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Factorizations and Accurate Computations with Min and Max Matrices

  • Khiar, Yasmina
  • Mainar, Esmeralda
  • Royo-Amondarain, Eduardo
Min and max matrices are structured matrices that appear in diverse mathematical and computational applications. Their inherent structures facilitate highly accurate numerical solutions to algebraic problems. In this research, the total positivity of generalized Min and Max matrices is characterized, and their bidiagonal factorizations are derived. It is also demonstrated that these decompositions can be computed with high relative accuracy (HRA), enabling the precise computations of eigenvalues and singular values and the solution of linear systems. Notably, the discussed approach achieves relative errors on the order of the unit roundoff, even for large and ill-conditioned matrices. To illustrate the exceptional accuracy of this method, numerical experiments on quantum extensions of Min and L-Hilbert matrices are presented, showcasing their superior precisions compared to those of standard computational techniques.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

On the accurate basis conversion of univariate polynomials

  • Khiar, Y.
  • Mainar, E.
  • Peña, J. M.
  • Royo-Amondarain, E.
  • Rubio, B.
This paper summarizes the bidiagonal factorizations of change of basis matrices between polynomial bases commonly used in interpolation and computer-aided geometric design. These factorizations enable the efficient and highly accurate resolution of linear algebra problems, offering significant advantages in terms of precision. The article also highlights a variety of applications, including the accurate computation of divided differences and the efficient solution of algebraic problems involving collocation matrices or Gram matrices, underscoring the practical relevance of these factorizations in mathematical and computational contexts.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Positive Hankel Matrices, Eigenvalues and Total Positivity

  • Peña, Juan Manuel
For positive Hankel matrices, an interval containing all eigenvalues is obtained. With a stronger condition, we also construct two sharper intervals for the eigenvalue localization. The total positivity of positive Hankel matrices is analyzed. The relationship between Hankel TP matrices and some Toeplitz SR matrices is analyzed.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Accurate determinant computation of Cauchy-polynomial matrices

  • Khiar, Yasmina
  • Mainar, Esmeralda
  • Peña, Juan Manuel
  • Royo-Amondarain, Eduardo
This paper investigates the factorization of Cauchy-polynomial matrices, a structured class that generalizes Cauchy-Vandermonde matrices by incorporating polynomial bases different from the monomial basis. We analyze the impact of different polynomial bases, including q-Bernstein, h-Bernstein, and Said-Ball polynomials, on numerical accuracy. A key focus is the derivation of formulas for their determinants, satisfying the No Inaccurate Cancellation condition and ensuring high relative accuracy. The sensitivity of the algorithm under deviations of the input data is analyzed, and an upper running error bound is provided. Theoretical findings are supported by numerical experiments, demonstrating the superior accuracy of the proposed determinant formulas compared to standard computational methods, even when perturbations are considered.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

An iterated greedy‐based metaheuristic with local search for the rank pricing problem

  • Calvete, Herminia I.
  • Galé, Carmen
  • Hernández, Aitor
  • Iranzo, José A.
The rank pricing problem involves determining optimal prices for a set of products while accounting for customers' budgets and preferences. This study develops an iterated greedy‐based metaheuristic to efficiently solve this problem. The core idea is to generate a sequence of solutions by iteratively applying destruction and reconstruction phases. In this process, some components of a solution are removed, yielding partial solutions from which complete solutions are reconstructed. A local search method with three neighborhood exploration strategies is then applied. Computational experiments demonstrate the effectiveness of the proposed algorithm by comparing its performance with exact and heuristic methods from the literature. It consistently finds optimal or near‐optimal solutions for instances with known optima. For most cases where the optimal solution is unknown, the algorithm matches or outperforms the best‐known solutions. Moreover, it achieves these results with significantly lower computational times, reinforcing its suitability for solving the rank pricing problem.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Domination in cylindrical graphs

Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

A novel approach to pessimistic bilevel problems. An application to the rank pricing problem with ties

  • Calvete, Herminia I.
  • Galé, Carmen
  • Hernández, Aitor
  • Iranzo, José A.
This paper introduces a novel method to address the pessimistic approach to the bilevel problem. It consists of considering a lexicographic biobjective optimization problem at the lower level. To emphasize the significance of this approach, we implement it in the context of the Rank Pricing Problem with Ties. This problem can be formulated as a bilevel problem that inherently demands the use of the pessimistic approach. Considering the properties of the lexicographic biobjective problem involved, we formulate this problem as a single level mixed integer optimization problem, deriving also valid values for the big-Ms involved and valid inequalities for this formulation. The computational experiment carried out confirms the relevance of the proposed method.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Bidiagonal Decompositions and Accurate Computations for the Ballot Table and the Fibonacci Matrix

  • Ballarín, Jorge
  • Delgado, Jorge
  • Peña, J. M.
Riordan arrays include many important examples of matrices. Here we consider the ballot table and the Fibonacci matrix. For finite truncations of these Riordan arrays, we obtain bidiagonal decompositions. Using them, algorithms to solve key linear algebra problems for ballot tables and Fibonacci matrices with high relative accuracy are derived. We include numerical experiments showing the accuracy of our method.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Accurate matrix conversion between Bernstein and ℎ-Bernstein bases

  • Khiar, Y.
  • Mainar, E.
  • Peña, J.M.
  • Royo-Amondarain, E.
This paper investigates the matrix conversion between the classical Bernstein basis and its oneparameter generalization, the ℎ-Bernstein basis. New ℎ-analogues of the binomial coefficients are introduced, providing explicit and compact expressions for the entries of the corresponding change-of-basis matrices. Structural properties such as symmetry and recurrence relations are derived, offering both theoretical insight and practical computational advantages. The proposed recurrence formulations enable the generation of the conversion matrices with high relative accuracy, avoiding subtractive cancellations and the numerical instabilities associated with direct collocation-based approaches. These results ensure reliable computations even for very large degrees and establish a foundation for the development of accurate and efficient algorithms in geometric modeling and related numerical applications involving ℎ-Bernstein polynomials. Numerical experiments confirm the theoretical findings and highlight the advantages of the proposed approach.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Perturbation theory and error analysis for the Cauchy formula

  • Díaz, Pablo
  • Khiar, Yasmina
  • Mainar, Esmeralda
  • Royo-Amondarain, Eduardo
In this work, we analyze the numerical behavior of the classical Cauchy identity & sum;(lambda )s(lambda)(a(1),... , a(n))s(lambda)(x(1), ... , x(m)) = & prod;(n)(j=1) & prod;(m)(i=1) 1/1-a(j)x(i), by developing perturbation and running error analyses. We show that relative perturbations in the nodes x(i) and coefficients a(j) only induce small relative changes in the output provided some relative gaps are sufficiently large. We also propose an algorithm computing a posteriori relative error bound with low computational overhead. Finally, we derive truncation error bounds for the Schur expansion of the formula. Numerical experiments confirm the sharpness of the theoretical results and illustrate the effectiveness of the proposed bounds in practice.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Generalized Capacitated Vertex Separator Problem: Models and Algorithms

  • Anglada, Sergio
  • Galé, Carmen
  • Salazar-González, Juan José
Given an undirected graph and two numbers q and b, the Capacitated Vertex Separation Problem (CVSP) looks for a vertex subset of minimum cardinality such that the connected components in the subgraph generated after the vertex removal can be packed into no more than q bins of cardinality at most b. This problem has been studied in graph theory, and most of the success in solving it is due to the hypothesis that the objective function minimizes the number of deleted vertices, that is, each node removal contributes identically to the objective function. In our work, this hypothesis is relaxed so each vertex has a cost and a weight, and the problem aims to minimize the total cost of the removed vertices while the total vertex weight in each bin is within the given capacity b, still limiting the number of bins to at most q. We introduce several mathematical formulations for the new problem, called the Generalized Capacitated Vertex Separator Problem (GCVSP), and analyze the performance of algorithms based on such formulations.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

High relative accuracy computations with covariance matrices of order statistics

  • Baz, Juan
  • Alonso, Pedro
  • Peña, Juan Manuel
  • Pérez-Fernández, Raúl
In many statistical applications, numerical computations with covariance matrices need to be performed. The error made when performing such numerical computations increases with the condition number of the covariance matrix, which is related to the number of variables and the strength of the correlation between the variables. In a recent work, a method for estimating the covariance matrix of a Gaussian Markov Random Field under a total positivity constraint was proposed. This estimation allows for performing many numerical computations with covariance matrices to high relative accuracy (the relative error is of the order of machine precision). However, the necessary conditions for this estimation method to produce a covariance matrix that is close to the population covariance matrix may be too demanding for real‐life data. In this paper, we study a particular setting related to order statistics in which these necessary conditions are inherently satisfied. In addition to the theoretical study, an extensive discussion concerning many potential applications is addressed, and a real‐life example of an application related to sports data is presented.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

An accurate method for the LU decomposition of amazing matrices

  • Ballarín, Jorge
  • Delgado, Jorge
  • Liu, Yanxin
  • Orera, Héctor
  • Peña, Juan Manuel
Amazing matrices arise in several important combinatorial problems. In [13], a question was raised concerning how to obtain an LU factorization of these matrices. In this work, we answer this question for the case and introduce a high relative accurate algorithm to compute such a factorization. Numerical experiments are provided to demonstrate the accuracy and effectiveness of the proposed method.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Accurate computations with Riordan arrays associated with Schröder matrices

  • Ballarín, Jorge
  • Delgado, Jorge
  • Peña, Juan Manuel
Large and little Schröder matrices as well as with their inverses are triangular matrices arising in Combinatorics. Through their total positivity and bidiagonal decomposition it is shown that their singular values, inverses and some associated linear systems can be solved with high relative accuracy. Numerical experiments confirm the theoretical results.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Total positivity of analytic bases through symmetric functions

  • Díaz, P.
  • Mainar, E.
This paper studies the bidiagonal factorization of the collocation matrices of analytic bases using symmetric functions. Explicit formulas for their initial minors are derived in terms of Schur functions. The structure of these formulas permits establishing sufficient conditions for the total positivity of generic systems of analytic functions. In addition, they have been found to lead to generalizations of the Cauchy identity for certain families of functions.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Accurate spectral computations and error analysis for r-geometric Min and Max matrices

  • Khiar, Y.
  • Mainar, E.
  • Royo-Amondarain, E.
In this work, we introduce a new two-parameter family of structured matrices, termed r-geometric Min and Max matrices, which generalize both the r-Min/r-Max and geometric Min/Max matrices. We derive explicit bidiagonal factorizations for these matrices using Neville elimination and establish necessary and sufficient conditions under which they are totally positive. Under these conditions, we develop algorithms capable of computing their eigenvalues and singular values to high relative accuracy, as well as closed-form expressions for their determinants. We also apply perturbation theory to analyze the sensitivity of these problems to input data, deriving structured condition numbers that quantify the impact of data perturbations. Numerical experiments confirm the theoretical results and demonstrate the reliability and efficiency of the proposed algorithms across both the general r-geometric case and key special instances.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Total positivity and high relative accuracy for a generalized Bernstein basis

  • Delgado, Jorge
  • Orera, Héctor
  • Peña, J.M.
The Bernstein basis of polynomials was generalized in Khosravian-Arabet al. (2018) in order to achieve better approximations than with classical Bernstein polynomials. We consider a family of those bases and prove their total positivity, which is very convenient in computer aided design. For adequate parameter values, we also obtain a subtraction-free algorithm for the bidiagonal decomposition of the corresponding collocation matrices, which allows us to derive accurate algorithms to compute all eigenvalues, all singular values or the inverse of such matrices. Numerical experiments confirm the high accuracy of our method.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Bidiagonal Decompositions and High‐Accuracy Computations for Newton Collocation Matrices

  • Mainar, E.
  • Marco, A.
  • Rubio, B.
  • Viaña, R.
We consider a class of collocation matrices associated with the Newton basis of the space of polynomials of degree at most , evaluated at a set of nodes. In the most general setting, we allow of these nodes to either coincide with or differ from those defining the Newton basis. We establish necessary and sufficient conditions for to be strictly totally positive (STP), based solely on an appropriate ordering of the nodes. We derive explicit formulas for the bidiagonal decomposition of and present an efficient algorithm for computing it to high relative accuracy (HRA). This factorization enables accurate and fast computation of solutions to linear systems with coefficient matrix , as well as the evaluation of its eigenvalues, singular values, and inverse, all to HRA. Furthermore, we apply our framework to the least squares approximation problem in the Newton basis. We show that the STP property of guarantees both uniqueness of the solution and, under mild conditions, its computation to an accuracy comparable to HRA. Extensive numerical experiments confirm the theoretical properties and demonstrate the superior accuracy and performance of the proposed algorithms when compared to standard numerical methods, especially in the presence of severe ill‐conditioning.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Making mosaics from Tetris® tiles

  • Calvete, Herminia I.
  • Hernández, Aitor
  • Iranzo, José A.
This paper addresses the problem of reproducing greyscale images using mosaics composed of tetromino tiles, the building blocks of the well-known puzzle game Tetris\textsuperscript{\textregistered}. An integer linear optimization model is proposed to minimize the discrepancy between the target image and the resulting mosaic. Three colouring schemes for assigning greyscale shades to the tetrominoes, together with three solution methods to manage the computational complexity of the model, are developed and assessed. Computational experiments on four images evaluate the proposed methods, combining image-similarity metrics with a user study gathering human preference judgements. The results identify the solution method that offers the best trade-off between mosaic quality and computational effort, while showing that the most suitable colouring scheme depends on the target image. Overall, the methodology provides a computationally efficient framework for generating visually coherent tetromino-based mosaics, even for images of realistic size and complexity.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

An exact and computationally efficient algorithm for balanced customer clustering under relocation constraints

  • Calvete, Herminia I.
  • Galé, Carmen
  • Iranzo, José A.
In logistics, customer clusters are often predefined based on geographic locations to optimize resource management and workload distribution. However, this approach frequently leads to significant cluster imbalance, particularly when not all customers require daily service or when operational constraints restrict the possibility of reallocating customers across clusters. These imbalances may affect workload equity, routing efficiency, and overall service performance. This paper addresses the problem of balancing customer clusters under relocation constraints by introducing two alternative criteria for measuring imbalance and enforcing them within a constrained reassignment framework. Our goal is to redistribute the set of customers so as to construct new clusters whose cardinalities are as balanced as possible while fully respecting the reassignment limitations. After formulating both nonlinear optimization models, we propose an exact algorithm that systematically reallocates customers through sequences of feasible moves, thereby ensuring progress toward a balanced configuration. We provide formal proofs showing that the algorithm always converges to an optimal solution for both imbalance criteria after a finite number of iterations. From these results, it follows that both models yield the same optimal solution. In addition, computational experiments demonstrate the efficiency of the method, showing that optimal solutions are obtained with very low running times for large-scale instances.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

A high-performance hybrid metaheuristic for the survivable one-fault-tolerant ring star problem

  • Calvete, Herminia I.
  • Galé, Carmen
  • Hernández, Aitor
  • Iranzo, José A.
The Ring Star Problem (RSP) arises in the design of communication and distribution networks that combine a ring connecting a subset of nodes, called hubs, that includes the depot, with star-shaped assignments of the remaining nodes, called terminals, to the hubs. To address survivability issues in such networks, the 1-Survivable Ring Star Problem (1-S-RSP) extends the classical RSP by enforcing survivability against the failure of at most one node, which means preserving the ring–star structure via the inclusion of additional edges and arcs. The resulting problem is computationally challenging due to the strong interdependence among ring construction, node assignments, and survivability requirements. In this paper, a hybrid metaheuristic based on evolutionary algorithms is proposed to efficiently solve the 1-S-RSP. The algorithm relies on a compact chromosome representation that encodes only hub-related information, while complete feasible solutions are constructed through dedicated procedures that determine the ring structure, backup edges, and terminal-to-hub assignments. The method is further enhanced by problem-specific local search mechanisms, including 2-opt and 3-opt backup procedures that explicitly account for survivability considerations. An extensive computational study is conducted on benchmark instances. After tuning the main design parameters of the algorithm, the proposed approach is evaluated against the best feasible solutions reported in the literature. The results show that the hybrid metaheuristic consistently produces solutions of comparable or superior quality, while requiring significantly shorter computing times. These outcomes demonstrate the effectiveness of the proposed method for addressing large-scale instances of the 1-S-RSP and highlight its potential for practical applications in survivable network design.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Efficient incremental non-dominated sorting for bi-objective problems via linear-space IDG representation

  • Lahoz, D.
  • Alberto, I.
  • Mateo, P. M.
This work presents an efficient incremental non-dominated sorting algorithm for bi-objective vectors. Non-dominated sorting algorithms organize solutions into layers, or Pareto fronts, based on dominance relations, and play a key role in the selection process of many well-known population-based algorithms for multi-objective optimization. Since the non-dominated sorting process is computationally expensive, its efficient design is of critical importance. The proposed algorithm is incremental, that is, given a population whose solutions are already assigned to layers, a new solution is incorporated and the dominance structure is updated as efficiently as possible, reconstructing the layers with minimal computational effort. The method is based on irreducible domination graphs of order 1, IDG, for which a storage structure requiring linear space in the number of solutions is introduced, instead of the quadratic requirements of the general case. Based on this representation, an incremental non-dominated sorting algorithm with O(n) complexity is developed, matching the complexity of well-known algorithms in the literature while relying on simpler data structures. Key components of the approach include locating the appropriate front for the new solution, managing displaced nodes across layers, and efficiently updating dominance relations. This linear complexity is achieved thanks to the structure of the IDG, which stores immediate dominance relations among solutions, i.e., the set of nodes in the previous Pareto layer that directly dominate each node.