Search

Technical report, A new method for computing the largest singular value \xi_1 and an associated right singular vector of a large and sparse complex matrix A is developed. The method accelerates a new method for computing \xi_1 and an associated right singular vector which converges from an initial random vector under the only condition that the initial vector has component in the eigenspace of A^HA associated with eigenvalue \xi_1^2, where A^H denotes the transpose conjugate of A. The storage required by the accelerated new method in addition to the storage of A includes for A large and sparse basically the storage of a few complex vectors of the column or row dimension of A. Using two benchmarks of large sparse nonsingular square Hermitian complex matrices with known singular values it is analyzed the accuracy and computational cost of the accelerated new method. Using standard floating-point arithmetic, the accelerated new method is able to compute xi_1 with slightly less than 8 decimal digits of accuracy in the worst case. The new method is in average somewhat faster than a method combining Lanczos without orthogonalization and inverse iteration, which can be regarded as a previous state-of-the-art method for A large and sparse with similar storage requirements as the new method and is very old (it was well understood in the late 70’s)., Postprint (updated version)

Una de les principals aspiracions de la ciència és la de determinar l’efecte causat per una acció en un context donat. Aquest problema sovint es pot modelar com una tasca de compleció de matrius. En els últims anys, s’han establert algunes connexi- ons entre la literatura de compleció de matrius i la seva naturalesa causal subjacent, en concret, els contrafactuals. En aquesta tesi, formalitzem aquestes afirmacions contrafactuals utilitzant models gràfics causals. En particular, proposem un nou marc teòric que relaciona els grafs causals amb factoritzacions de matrius. Demos- trem que, sota certes hipòtesis, la nostra configuració indueix una descomposició que porta a determinats algorismes de compleció. Finalment, mostrem que els algo- rismes relacionats amb aquestes factoritzacions són competitius amb altres mètodes tradicionals en les dades de PRISM, que busca descobrir el potencial anticancerigen de medicaments no oncològics., Una de las aspiraciones principales en la ciencia es la de determinar el efecto causado por una acción en un contexto dado. A menudo, este problema se puede modelar como una tarea de completación de matrices, donde las filas están indexadas por acciones, las columnas están indexadas por contextos, y las entradas de la matriz co- rresponden a una cantidad de nuestro interés. En los últimos años, se han establecido algunas conexiones entre la literatura de completación de matrices y su naturaleza causal subyacente, en concreto, los contrafactuales. En esta tesis, formalizamos es- tas afirmaciones contrafactuales utilizando modelos gráficos causales. En particular, proponemos un nuevo marco teórico que relaciona los grafos causales con factoriza- ciones de matrices. Demostramos que, bajo ciertas hipótesis, nuestra configuración induce una descomposición que lleva a determinados algoritmos de completación. Fi- nalmente, mostramos que los algoritmos relacionados con estas factorizaciones son competitivos con otros métodos tradicionales en los datos de PRISM, cuyo fin es el de descubrir el potencial anticancerígeno de medicamentos no oncológicos., Determining the effect of an action in a given context is a principal goal in science. This problem can often be modeled as a matrix completion task, where the rows are indexed by actions, the columns are indexed by contexts, and the matrix entries correspond to an outcome of interest. In the past years, there have been some con- nections between the matrix completion literature and its underlying causal nature, namely counterfactuals. In this thesis, we formalize these counterfactual statements using causal graphical models. In particular, we provide a new theoretical framework that connects causal graphs with factor models. We show that, under a linearity assumption, this setup induces a decomposition over the matrix of outcomes, which naturally leads to particular completion approaches. Finally, we demonstrate that the algorithms related to these factor models are competitive with other traditional methods on the PRISM Repurposing dataset, which attempts to discover the anti- cancer potential of non-oncology drugs., Outgoing

PhysiCell/BioFVM is an opopen-sourcend agent-based software package supporting 2D/3D simulations for multi-cellular biological systems. It is completely written in C++ and enjoys shared-memory parallelization through OpenMP. An attempt is being made to re-structure the code-base to add support for Distributed parallelization through MPI. The biggest bottleneck in the current version of the simulation package is the serial Thomas solver that is used to solve the triadiagonal system of linear equations resulting from the Finite Volume Discretization Method (FVM) of the reaction-diffusion equations modelling the secretion, ingestion of substrates from cells/agents. Our aim in this project is to replace the serial solver with an efficient distributed-parallel solver. For this purpose we experiment with the Cyclic Reduction (CR) algorithm on a shared-memory system but after understanding its limitations with regard to the problem size, we settle on a modified version of the Thomas solver as our preferred choice in distributed-parallel settings. Our experiments show that the Cyclic Reduction algorithm implemented using OpenMP is able to outperform the serial Thomas solver at a certain thread count on a single node. However, we do not extend this algorithm to support distributed parallelism due to the aforementioned problem. Further, we implement an MPI-only version of the modified Thomas algorithm that promises good scalability on multiple nodes of our HPC cluster - the MareNostrum 4 (MN4) supercomputer at the Barcelona Supercomputing Center (BSC). We project and optimistically conclude that for large problem sizes and a high core count, the parallel modified Thomas algorithm can offer significant reduction in the time to solution for complex 3D simulations in PhysiCell/BioFVM.

Explicit expressions for the coefficients of the group inverse of a circulant matrix depending on four complex parameters are analytically derived. The computation of the entries of the group inverse are now reduced to the evaluation of a polynomial. Moreover, our methodology applies to both the invertible and the singular case, the latter being computationally less expensive. The techniques we use are related to the solution of boundary value problems associated with second order linear difference equations., Peer Reviewed, Postprint (published version)

A square symmetric matrix A is said bisymmetric if AS=SA, whereS is the matrix with ones along the secondary diagonal and zeroselsewhere. We denote by J(a,b) the real symmetric Jacobi matrixwith main diagonala= (a0, a1, . . . , an) and second diagonalb=(b0, b1, . . . , bn-1). Hoschtadt and Hald proved that the spectrum ofa bisymmetric Jacobi matrix with nonnegative off-diagonal elementsdefines uniquely the matrix and they give a constructive proof of theresult. We characterize the spectra of nonnegative irreducible bisym-metric Jacobi matrices of size lees or equal 5, and we give the uniqueentries of the matrix in terms of the eigenvalues.We also parametrize the set of monic polynomials of degree n whoseroots strictly interlace a given set ¿ ofn+ 1 ordered real numbers,and we use this parametrization to characterize the symmetric Jacobimatrices realizing ¿. Our development is strongly based on the workby Hoschtadt but, instead of considering principal submatrices, we usethe above parametrization of monic polynomials interlacing ¿., Postprint (published version)

The need of solving linear systems with circulant matrices occursin many problems related to the periodicity of that problem. This class ofsystem appears in many applications that range from numerical solution ofpartial differential equations with periodic boundary conditions, until codingtheory, statistics, time series analysis, image processing, or when we approx-imate periodic functions with splines. In spite the problem of computing thegroup inverse of a circulant matrix of order n can be considered solved froma theoretical or algebraic point of view, even for low dimensions the com-putational cost to find the solution could be very high, typically with orderO(n2).Different approches to compute the inverse of a circulant matrix have focusedon special classes of circulant matrices. For structured matrices with threeparameters the application of the FFT, leads to algorithms to solve circulantsystems with orderO(nlog2n) and moreover the proper election of circulantpreconditioners can reduce the computation to orderO(n).In this communication we present our last advances on the computation of thegroup inverse of a family of circulant matrices with four complex parameters.Specifically, we obtain analytical expressions for the coefficients of their groupinverse. This means that by just checking some relations between the fourcoefficients we can explicitly compute the coefficients of the group inverse andthere is no need to apply any numerical method to compute them. Therefore,we improve the computational cost of computing the group inverse of thisclass of matrices that, in the worst case, is now reduced to the evaluationof a polynomial. Moreover our methodology applies to both the invertibleand the singular case, the latter being computationally less expensive. Thetechniques we use are related with the solution of boundary value problemsassociated with first or second order linear difference equations and henceinvolve the evaluation of Chebyshev polynomials., Postprint (published version)

Sparse matrix operations are critical kernels in multiple application domains such as High Performance Computing, artificial intelligence and big data. Vector processing is widely used to improve performance on mathematical kernels with dense matrices. Unfortunately, existing vector architectures do not cope well with sparse matrix computations, achieving much lower performance in comparison with their dense counterparts.To overcome this limitation, we present the Vector Indexed Architecture (VIA), a novel hardware vector architecture that accelerates applications with irregular memory access patterns such as sparse matrix computations. There are two main bottlenecks when computing with sparse matrices: irregular memory accesses and index matching. VIA addresses these two bottlenecks with a smart scratchpad that is tightly coupled to the Vector Functional Units within the core.Thanks to this structure, VIA improves locality for sparse-dense computations and improves the index matching search process for sparse computations. As a result, VIA achieves significant performance speedup over highly optimized state-of-the-art C++ algebra libraries. On average, VIA outperforms sparse matrix vector multiplication, sparse matrix addition and sparse matrix matrix multiplication kernels by 4.22 ×, 6.14 × and 6.00 ×, respectively, when evaluated over a thousand sparse matrices that arise in real applications. In addition, we prove the generality of VIA by showing that it can accelerate histogram and stencil applications by 4.5 × and 3.5 ×, respectively., This work has been supported by the European HiPEAC Network of Excellence, by the Spanish Ministry of Science and Innovation (contract TIN2015-65316-P), by the Generalitat de Catalunya (contracts 2017-SGR-1414 and 2017-SGR-1328), and by the DRAC project, which is co-financed by the European Union Regional Development Fund within the framework of the ERDF Operational Program of Catalonia 2014-2020 with a grant of 50% of total eligible cost. A. Barredo has been supported by the Spanish Government under Formation del Personal Investigador fellowship number BES-2017- 080635. M. Moreto has been partially supported by the Spanish Ministry of Economy, Industry and Competitiveness under Ramon y Cajal fellowship number RYC-2016-21104., Peer Reviewed, Postprint (author's final draft)

We present a necessary and sufficient condition for the singularity of circulant matrices associated with directed weighted cycles. This condition is simple and independent of the order of matrices from a complexity point of view. We give explicit and simple formulas for the Drazin inverse of these circulant matrices. We also provide a Bjerhammar-type condition for the Drazin inverse., Peer Reviewed, Postprint (published version)

In community networks, users access the web using a proxy selected from a list, normally without regard to its performance. Knowing which proxies offer good response times for each client would improve the user experience when navigating, but would involve intensive probing that would in turn cause performance degradation of both proxies and the network. This paper explores the feasibility of estimating the response times for each client/proxy pair by probing only a few of the existing pairs and then using matrix factorization. To do so, response times are collected in a community network emulated on a testbed platform, then a small part of these measurements are used to estimate the remaining ones through matrix factorization. Several algorithms are tested; one of them achieves estimation accuracy with low computational cost, which renders its use feasible in real networks, Peer Reviewed, Postprint (published version)

The Dynamic OD Matrix Estimation (DODME) is a hard problem since no direct full observations are available, and therefore one should resort to indirect estimation approaches. This formulation solves at the upper level a nonlinear optimization that minimizes some distance measures between observed and estimated link flow counts at certain counting stations located in a subset of links in the network, and at the lower level a traffic assignment that estimates these link flow counts assigning the current estimated matrix. Since these estimations are based on a traffic assignment at the lower level, these analytical approaches, although numerically efficient, imply a high computational cost. The advent of ICT applications has made available new sets of traffic related measurements enabling new approaches. This research report explores how to extract such information from the recorded data., Dynamic traffic models require dynamic inputs, and one of the main inputs are the Dynamic Origin-Destinations (OD) matrices describing the variability over time of the trip patterns across the network. The Dynamic OD Matrix Estimation (DODME) is a hard problem since no direct full observations are available, and therefore one should resort to indirect estimation approaches. Among the most efficient approaches, the one that formulates the problem in terms of a bilevel optimization problem has been widely used. This formulation solves at the upper level a nonlinear optimization that minimizes some distance measures between observed and estimated link flow counts at certain counting stations located in a subset of links in the network, and at the lower level a traffic assignment that estimates these link flow counts assigning the current estimated matrix. The variants of this formulation differ in the analytical approaches that estimate the link flows in terms of the assignment and their time dependencies. Since these estimations are based on a traffic assignment at the lower level, these analytical approaches, although numerically efficient, imply a high computational cost. The advent of ICT applications has made available new sets of traffic related measurements enabling new approaches; under certain conditions, the data collected on used paths could be interpreted as an, de facto, estimated assignment observed . This allows extracting empirically the same information provided by an assignment that is used in the analytical approaches. This research report explores how to extract such information from the recorded data., This research was funded by PTV Group, by TRA2016-76914-C3-1-P Spanish R+D Programs and by Secretaria d’Universitats-i-Recerca-Generalitat de Catalunya- 2017- SGR- 1749 and Industrial PhD Program 2017 DI 041., Preprint

In vibration control of compound structures, inter-substructure damper (ISSD) systems exploit the out-of-phase response of different substructures to dissipate the kinetic vibrational energy by means of inter-substructure damping links. For seismic protection of multistory buildings, distributed sets of interstory fluid viscous dampers (FVDs) are ISSD systems of particular interest. The connections between distributed FVD systems and decentralized static output-feedback control allow using advanced controller-design methodologies to obtain passive ISSD systems with high-performance characteristics. A major issue of that approach is the computational dificulties associated to the numerical solution of optimization problems with structured bilinear matrix inequality constraints. In this work, we present a novel iterative linear matrix inequality procedure that can be applied to obtain enhanced suboptimal solutions for that kind of optimization problems. To demonstrate the effectiveness of the proposed methodology, we design a system of supplementary interstory FVDs for the seismic protection of a five-story building by synthesizing a decentralized static velocity-feedback H∞ controller. In the performance assessment, we compare the frequency-domain and time-domain responses of the designed FVD system with the behavior of the optimal static state-feedback H∞ controller. The obtained results indicate that the proposed approach allows designing passive ISSD systems that are capable to match the level of performance attained by optimal state-feedback active controllers., This research was partially supported by the Spanish Ministry of Economy and Competitiveness under Grant DPI2015-64170-R/FEDER and by the Italian Ministry of Education, University and Research under the Project “Department of Excellence LIS4.0—Lightweight and Smart Structures for Industry 4.0”, Peer Reviewed, Postprint (published version)

A complex matrix pencil A-¿B is called structurally stable if there exists its neighborhood in which all pencils are strictly equivalent to this pencil. We describe all complex matrix pencils that are structurally stable. It is shown that there are no pairs (M,N) of m × n and n × m complex matrices (m, n = 1) that are structurally stable under the contragredient equivalence (S-1MR,R-1NS) in which S and R are nondegenerate, Peer Reviewed, Postprint (author's final draft)

We present here necessary and sufficient conditions for the invertibility of some circulant matrices that depend on three parameters and moreover, we explicitly compute the inverse. Our study also encompasses a wide class of circulant symmetric matrices. The techniques we use are related with the solution of boundary value problems associated to second order linear difference equations. Consequently, we reduce the computational cost of the problem. In particular, we recover the inverses of some well known circulant matrices whose coefficients are arithmetic or geometric sequences, Horadam numbers among others. We also characterize when a general symmetric, circulant and tridiagonal matrix is invertible and in this case, we compute explicitly its inverse., Postprint (published version)

Postprint (published version)

Postprint (published version)

We address the reduction to compact band forms, via unitary similaritytransformations, for the solution of symmetric eigenvalue problems and the compu-tation of the singular value decomposition (SVD). Concretely, in the first case, werevisit the reduction to symmetric band form, while, for the second case, we pro-pose a similar alternative, which transforms the original matrix to (unsymmetric)band form, replacing the conventional reduction method that produces a triangular–band output. In both cases, we describe algorithmic variants of the standard Level3 Basic Linear Algebra Subroutines (BLAS)-based procedures, enhanced with look-ahead, to overcome the performance bottleneck imposed by the panel factorization., Peer Reviewed, Postprint (author's final draft)

“This is a post-peer-review, pre-copyedit version of an article published in Ukrainian Mathematical Journal. The final authenticated version is available online at: http://dx.doi.org/ 10.1007/s11253-019-01676-x, A complex matrix pencil A-¿B is called structurally stable if there exists its neighborhood in which all pencils are strictly equivalent to this pencil. We describe all complex matrix pencils that are structurally stable. It is shown that there are no pairs (M,N) of m×n and n×m complex matrices (m,n=1) that are structurally stable under the contragredient equivalence (S-1MR,R-1NS), in which S and R are nonsingular., Peer Reviewed, Postprint (author's final draft)

We present here the necessary and sufficient conditions for the invertibility of tridiagonal matrices, commonly named Jacobi matrices, and explicitly compute their inverse. The techniques we use are related with the solution of Sturm–Liouville boundary value problems associated to second order linear difference equations. These boundary value problems can be expressed throughout a discrete Schrödinger operator and their solutions can be computed using recent advances in the study of linear difference equations. The conditions that ensure the uniqueness solution of the boundary value problem lead us to the invertibility conditions for the matrix, whereas the solutions of the boundary value problems provide the entries of the inverse matrix, Peer Reviewed, Postprint (author's final draft)

This paper addresses the design of a state-feedback controller for a class of nonlinear parameter varying (NLPV) systems in which the nonlinearity can be expressed as a parameter-varying Lipschitz term. The controller is designed to satisfy a D-stability specification, which is akin to imposing constraints on the closed-loop pole location in the case of LTI and LPV systems. The design conditions, obtained using a quadratic Lyapunov function, are eventually expressed in terms of linear matrix inequalities (LMIs), which can be solved efficiently using available solvers. The effectiveness of the proposed method is demonstrated by means of a numerical example., Postprint (author's final draft)

This is a post-peer-review, pre-copyedit version of an article published in Journal of algebraic combinatorics. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10801-018-0862-y, We present a method to derive the complete spectrum of the lift Ga of a base digraph G, with voltage assignment a on a (finite) group G. The method is based on assigning to G a quotient-like matrix whose entries are elements of the group algebra C[G], which fully represents Ga. This allows us to derive the eigenvectors and eigenvalues of the lift in terms of those of the base digraph and the irreducible characters of G. Thus, our main theorem generalizes some previous results of Lov´asz and Babai concerning the spectra of Cayley digraphs, Peer Reviewed, Postprint (author's final draft)

We tackle the obtaining of canonical forms for classifying linear control systems with regard to changes in the state variables. Although it was solved in the 1980s for controllable systems, it is still an open problem for the general case of multiparametric non-necessarily controllable systems. Here we obtain a general reduced form which is canonical for a class of systems which includes the cases already known (uniparametric systems, controllable systems), Peer Reviewed, Postprint (published version)

El objetivo actual del proyecto es estudiar de forma comparativa tres matrices porosas: un hidrogel preparado por entrecruzamiento, una matriz de microfibras preparas por electrospinning, y una matriz porosa preparada por solving-casting y agente porogénico. El hidrogel será preparado con una nueva poliesteramida (PEA) denominada PEA-4F4 sintetizada a partir de una diéster (4C), el aminoácido fenilanina (F), y un diol insaturado (4C), y como agenete entrecruzante se usará el polietilenglicol (PEG). La matriz de fibras será preparada a partir de la mezcla del polibutilensuccinato (PBS) y la PEA-8L6 (diéster de 8 C, aminoácido leucina, diol de 6C) (PBS:PEA, 50-50 wt%). Finalmente la matrcon agente porogénico (NaCl) será preparada por evaporación del solvente (cloroformo) de una disolución de PBS:PEA-8L6:NaCl, 40:40 wt% en la cual se resuspende partículas de Nacl al 20%. Estas matrices serán estudiadas como sistemas de liberadores de drogas al ser cargadas al 3 wt% con el antitumoral curcumina.

Montse Pallàs 4 de nov. 2019 13:31 “This is a post-peer-review, pre-copyedit version of an article published in Revista de la Real Academia de Ciencias Exactas, Físicas y Naturales. Serie A. Matemáticas (Online). The final authenticated version is available online at: http://dx.doi.org/10.1007/s13398-019-00754-w, Analysis of spectra of families of sets of matrices verifying certain properties is not simple because phenomena as singularities and bifurcations appear. An excellent tool for the analysis can be making use of versal deformations because of the spectrum of the family coincides with the spectrum of its versal deformation. Disposing of a versal deformation is advantageous since any perturbation of an element can be described up to equivalence by its versal deformation, and it gives the possibility to calculate bifurcation diagrams of families of elements in general position. V.I. Arnold constructed versal deformations, of a differentiable family of square matrices under conjugation and his techniques have been generalised to different cases as to matrix pencils under the strict equivalence, for example. In this paper, we present versal deformations of elements of the Lie algebra consisting of triples of traceless matrices to coefficients on $\mathbb{F} =\mathbb{ C}$ or $\mathbb{R}$, which are simultaneously diagonalizable. Study families of traceless matrix triples have great interest because the Lie algebra is related to gauge fields because they appear in the Lagrangian describing the dynamics of the field, then they are associated to 1-forms that take values on a certain Lie algebra. It is also of interest to note that triples of traceless matrices have some relevance for supergravity theories. Another application is found when we must give the instanton solution of Yang-Mills field can be presented in an octonion form, and it can be represented by triples of traceless matrices., Peer Reviewed, Postprint (author's final draft)

This is an Accepted Manuscript of a book chapter published by Routledge/CRC Press in Advances in Engineering Materials, Structures and Systems: Innovations, Mechanics and Applications on 21 August 2019, available online: https://www.taylorfrancis.com/books/9780429426506, In this paper, we present a novel Iterative Linear Inequality (ILMI) strategy for controller design that makes it possible to compute suboptimal H-infinity static output-feedback (SOF) controllers with high-performance characteristics. The obtained SOF controllers can be effective in reducing the vibrational response of multi-degree-of-freedom structures subjected to broad-band excitations. To demonstrate the effectiveness of the proposed methodology, a SOF controller is designed for the seismic protection of a multi-actuated five-story shear-frame structure with positive result., Peer Reviewed, Postprint (author's final draft)

Given the Laplacian matrix associated to a weighted graph and given x a single vertex of it, the bottleneck matrix (related to x) is the inverse matrix of the sub matrix of the Laplacian obtained by eliminating the row and the column corresponding to x. The bottleneck matrix is used to calculate the group inverse of the initial Laplacian matrix, for instance. In this work we have managed to generalize this situation twofold: in the sense of considering symmetric M–matrices related to Schr¨odinger operators acting on networks (doubly weighted graphs, where not only edges but also vertices are discriminated) and also by using sub-matrices of the initial one in which two, three or more rows and columns are erased, those corresponding to two, three or more vertices. We conceive that every symmetric M–matrix corresponds to a network where both a conductance on the edges and a weight on the vertices are introduced. Solving boundary value problems for Schr¨odinger’s operators throughout the whole network or just a part of it, we find the relation between the corresponding group inverse and inverse matrices respectively. Since the part of the network to be considered is arbitrary, the reduction in the order of the matrices is also arbitrary. The work is finished by exposing the application of our result to the calculation of the Green function of a path., Postprint (published version)