[EN] The essential topic of this memory is the study of H-matrices as they were introduced by Ostrowski and hereinafter extended and developed by different authors. In this study three slopes are outlined: 1) the iterative or automatic determination of H-matrices, 2) the properties inherent in the H-matrices and 3) the matrices related to H-matrices. H-matrices acquire every time major relevancy due to the fact that they arise in numerous applications so much in Mathematics, since in the Industry between. Between these applications we can mention the following ones: 1) in the discretization of certain parabolic non-linear equations, 2) in the system resolution of linear equations, assuring his presence the convergence of iterative classic methods and 3) in the resolution of problems of free contour in Analysis of Fluids. It is very important to observe that some H-matrices transform in H- matrices for the action of some matrix operation on them. Such it is the case of the matrix operation known as Hadamard's Product, that is to say, the product element to element of two matrices. If this product realizes between the elements of a matrix and the elements of its inverse transpose then this matrix product is called combined matrix. The combined matrix is an H- matrix under certain conditions of the original matrix and, in addition, the combined matrix is linked to applications very important as the Relative Gain in chemical processes or the relation between the eigenvalues of the original matrix and the elements of a diagonalizable matrix. In addition, provided that the sum of every row and of every column is equal to one, in those cases in which the combined matrix is not negative, C(A) is a doubly stochastic matrix and therefore it is of great usefulness in the Statistical Theory. The present memory is structured of the following way. In the first chapter, after the introduction, we present the notation, the basic concepts and previous results developed by other authors and that are going to be used largely in the memory. xiii xiv In the Chapter 2 we present and analyze different algorithms that have been proposed by the aim to determine when a given matrix is or is not an H-matrix. It is emphasized in the study of those algorithms that have turned out to be the most efficient and in the most relevant part of this chapter we present a new algorithm that turns out to be a contribution to the literature of the algorithms for the determination or identification of H-matrices, as well as of his character. In the Chapter 3 we widely studied the combined matrix of a nonsingular H-matrices and we obtain new and important properties of the combined matrix of H-matrices. In the Chapter 4 we calculate the combined matrix of diagonally dominant and equipotent matrices and also we obtain new and important results that relate the combined matrix of these diagonally dominant and equipotent matrices to H-matrices. In Chapter 5, like summary, we outline the principal achievements reached during the development of this memory and, in addition, enumerate the works on which already we are working and also we present some of the principal lines of investigation for the near future. Finally, in the appendices we present, in format MATLAB, different algorithms studied in Chapter 2 that make the automatic determination of H-matrices as a purpose. Especially, is outlined the codification of the new algorithm proposed with each of its parts in the correct order to be run in the computer. / [ES] El tema esencial de esta memoria es el estudio de las H-matrices tal y como fueron introducidas por Ostrowski y más adelante ampliadas y desarrolladas por diferentes autores. En ese estudio se destacan tres vertientes: 1) la determinación iterativa o automática de las H-matrices, 2) las propiedades inherentes a las H- matrices y 3) las matrices relacionadas con las H-matrices. Las H-matrices adquieren cada vez mayor relevancia debido a que surgen en numerosas aplicaciones tanto en la ciencia Matemática como en la Industria. Entre esas aplicaciones podemos citar las siguientes: 1) en la discretización de ciertas ecuaciones parabólicas no lineales, 2) en la resolución de sistemas de ecuaciones lineales, asegurando su presencia la convergencia de métodos iterativos clásicos y 3) en la resolucion de problemas de contorno libre en Análisis de Fluidos. Es de suma importancia observar que algunas matrices devienen en H- matrices por la acción de alguna operación matricial sobre ellas. Tal es el caso de la operación matricial conocida como Producto de Hadamard, es decir, el producto elemento a elemento de dos matrices. Si este producto se realiza entre los elementos de una matriz y los elementos de su matriz inversa traspuesta, entonces la matriz producto, denominada Matriz Combinada, puede ser una H-matriz bajo determinadas condiciones de la matriz original y, además, la matriz combinada está vinculada a aplicaciones muy importantes como la Ganancia Relativa en procesos químicos o la relación entre los valores propios de la matriz original y los elementos de una matriz diagonalizable. Además, dado que la suma de cada fila y de cada columna de una matriz combinada es exactamente igual a 1, en aquellos casos en que la matriz combinada sea no negativa, C(A) es una matriz doblemente estocástica y por tanto puede ser de gran utilidad en Estadística y Probabilidad. La memoria está estructurada por capítulos de la siguiente manera. En cada uno de ellos se presentan las aportaciones de la misma. ix x En el Capítulo 1, luego de la introducción, se da la notación y se definen los conceptos básicos y, además, se enuncian los resultados previos de ámbito general desarrollados por otros autores y que van a ser utilizados en gran parte de la memoria. En el Capítulo 2 se presentan y analizan diferentes algoritmos que han sido propuestos con el objetivo de determinar cuándo una matriz dada es o no es una H-matriz. Se hace hincapié en el estudio de aquellos algoritmos que han resultado ser los más eficientes y en la parte más relevante de este capítulo se presenta un nuevo algoritmo de menor coste computacional que los anteriores y más sencillo de programar, que resulta ser un aporte a la literatura de los algoritmos para la determinación o identificación de las H-matrices, así como de su carácter y también determina los bloques diagonales irreducibles. En el Capítulo 3 se estudia ampliamente la matriz combinada de H- matrices no singulares y se obtienen también nuevos e importantes resultados sobre las propiedades de la matriz combinada de H-matrices. Se demuestra que la matriz combinada de una H-matriz de la clase invertible es también H-matriz de la misma clase. Además, se prueba que la matriz combinada de una H-matriz de la clase mixta no singular es también H-matriz. En el Capítulo 4 se calcula la matriz combinada de matrices diagonalmente dominantes equipotentes. En particular, se demuestra que la matriz combinada de una H-matriz, denominada DmP es siempre una H-matriz de la clase mixta pero singular. Para otras H-matrices que no son DmP se prueba que su matriz combinada es H-matriz de la clase invertible. Se conjetura que todas las H-matrices de la clase mixta que no son DmP tienen esta última propiedad. En el Capítulo 5 se recogen, a modo de resumen, los principales logros alcanzados durante el desarrollo de esta memoria y, además, se enumeran los trabajos sobre los cuales ya se está trabajand / [CAT] El tema essencial d'aquesta memòria és l'estudi de les H-matrius tal com van ser introduïdes per Ostrowski i més endavant ampliades i desenvolupades per diferents autors. En aqueix estudi es destaquen tres vessants: 1) la determinació iterativa o automàtica de les H-matrius, 2) les propietats inherents a les H-matrius i 3) les matrius relacionades amb les H-matrius. Les H-matrius adquireixen cada vegada major rellevància a causa que sorgeixen en nombroses aplicacions tant en la ciència Matemàtica com en la Indústria. Entre aqueixes aplicacions podem citar les següents: 1) en la discretització de certes equacions parabòliques no-lineals, 2) en la resolució de sistemes d'equacions lineals, assegurant la seua presència la convergència de mètodes iteratius clàssics i 3) en la resolució de problemes de contorn lliure en Anàlisi de Fluids. És de summa importància observar que algunes matrius esdevenen en H-matrius per l'acció d'alguna operació matricial sobre elles. Tal és el cas de l'operació matricial coneguda com a Producte de Hadamard, és a dir, el producte element a element de dues matrius. Si aquest producte es realitza entre els elements d'una matriu i els elements de la seua matriu inversa trasposada, llavors la matriu producte, denominada Matriu Combinada, pot ser una H-matriu sota determinades condicions de la matriu original i, a més, la matriu combinada està vinculada a aplicacions molt importants com el Guany Relatiu en processos químics o la relació entre els valors propis de la matriu original i els elements d'una matriu diagonalitzable. A més, atès que la suma de cada fila i de cada columna d'una matriu combinada és exactament igual a 1, en aquells casos en què la matriu combinada siga no negativa, C(A) és una matriu doblement estocàstica i per tant pot ser de gran utilitat en Estadística i Probabilitat. La memòria està estructurada per capítols de la següent manera. En cadascun d'ells es presenten les aportacions de la mateixa. En el Capítol 1, després de la introducció, es dóna la notació i es defixi xii neixen els conceptes bàsics i , a més, s'enuncien els resultats previs d'àmbit general desenvolupats per altres autors i que van a ser utilitzats en gran part de la memòria. En el Capítol 2 es presenten i analitzen diferents algorismes que han sigut proposats amb l'objectiu de determinar quan una matriu donada és o no és una H-matriu. Es posa l'accent en l'estudi d'aquells algorismes que han resultat ser els més eficients i en la part més rellevant d'aquest capítol es presenta un nou algorisme de menor cost computacional que els anteriors i mes senzill de programar, que resulta ser una aportació a la literatura dels algorismes per a la determinació o identificació de les H-matrius, així com del seu caràcter i també determina els blocs diagonals irreductibles. En el Capítol 3 s'estudia àmpliament la matriu combinada d'H-matrius no singulars i s'obtenen també nous i importants resultats sobre les propietats de la matriu combinada d'H-matrius. Es demostra que la matriu combinada d'una H-matriu de la classe invertible és també H-matriu de la mateixa classe. A més, es prova que la matriu combinada d'una H-matriu de la classe mixta no singular és també H-matriu. En el Capítol 4 es calcula la matriu combinada de matrius diagonalment dominants equipotents. En particular, es demostra que la matriu combinada d'una H-matriu, denominada DmP és sempre una H-matriu de la classe mixta però singular. Per a altres H-matrius que no són DmP es prova que la seua matriu combinada és H-matriu de la classe invertible. Es conjectura que totes les H-matrius de la classe mixta que no són DmP tenen aquesta última propietat. En el Capítol 5 s'arrepleguen, a manera de resum, els principals assoliments aconseguits durant el desenvolupament d'aquesta memòria i, a més, s'enumeren els treballs sobre els quals ja s'està treballant i s'esbossen algunes de les principal / Scott Guilleard, JA. (2015). Determinación y propiedades de H-matrices [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/58766 / TESIS

De nombreux phénomènes physiques peuvent être étudiés au moyen de modélisations et de simulations numériques, courantes dans les applications scientifiques. Pour être calculable sur un ordinateur, des techniques de discrétisation appropriées doivent être considérées, conduisant souvent à un ensemble d’équations linéaires dont les caractéristiques dépendent des techniques de discrétisation. D’un côté, la méthode des éléments finis conduit généralement à des systèmes linéaires creux, tandis que les méthodes des éléments finis de frontière conduisent à des systèmes linéaires denses. La taille des systèmes linéaires en découlant dépend du domaine où le phénomène physique étudié se produit et tend à devenir de plus en plus grand à mesure que les performances des infrastructures informatiques augmentent. Pour des raisons de robustesse numérique, les techniques de solution basées sur la factorisation de la matrice associée au système linéaire sont la méthode de choix utilisée lorsqu’elle est abordable. A cet égard, les méthodes hiérarchiques basées sur de la compression de rang faible ont permis une importante réduction des ressources de calcul nécessaires pour la résolution de systèmes linéaires denses au cours des deux dernières décennies. Pour les systèmes linéaires creux, leur utilisation reste un défi qui a été étudié à la fois par la communauté des matrices hiérarchiques et la communauté des matrices creuses. D’une part, la communauté des matrices hiérarchiques a d’abord exploité la structure creuse du problème via l’utilisation de la dissection emboitée. Bien que cette approche bénéficie de la structure hiérarchique qui en résulte, elle n’est pas aussi efficace que les solveurs creux en ce qui concerne l’exploitation des zéros et la séparation structurelle des zéros et des non-zéros. D’autre part, la factorisation creuse est accomplie de telle sorte qu’elle aboutit à une séquence d’opérations plus petites et denses, ce qui incite les solveurs à utiliser cette propriété et à exploiter les techniques de compression des méthodes hiérarchiques afin de réduire le coût de calcul de ces opérations élémentaires. Néanmoins, la structure hiérarchique globale peut être perdue si la compression des méthodes hiérarchiques n’est utilisée que localement sur des sous-matrices denses. Nous passons en revue ici les principales techniques employées par ces deux communautés, en essayant de mettre en évidence leurs propriétés communes et leurs limites respectives, en mettant l’accent sur les études qui visent à combler l’écart qui les séparent. Partant de ces observations, nous proposons une classe d’algorithmes hiérarchiques basés sur l’analyse symbolique de la structure des facteurs d’une matrice creuse. Ces algorithmes s’appuient sur une information symbolique pour grouper les inconnues entre elles et construire une structure hiérarchique cohérente avec la disposition des non-zéros de la matrice. Nos méthodes s’appuient également sur la compression de rang faible pour réduire la consommation mémoire des sous-matrices les plus grandes ainsi que le temps que met le solveur à trouver une solution. Nous comparons également des techniques de renumérotation se fondant sur des propriétés géométriques ou topologiques. Enfin, nous ouvrons la discussion à un couplage entre la méthode des éléments finis et la méthode des éléments finis de frontière dans un cadre logiciel unique. / Many physical phenomena may be studied through modeling and numerical simulations, commonplace in scientific applications. To be tractable on a computer, appropriated discretization techniques must be considered, which often lead to a set of linear equations whose features depend on the discretization techniques. Among them, the Finite Element Method usually leads to sparse linear systems whereas the Boundary Element Method leads to dense linear systems. The size of the resulting linear systems depends on the domain where the studied physical phenomenon develops and tends to become larger and larger as the performance of the computer facilities increases. For the sake of numerical robustness, the solution techniques based on the factorization of the matrix associated with the linear system are the methods of choice when affordable. In that respect, hierarchical methods based on low-rank compression have allowed a drastic reduction of the computational requirements for the solution of dense linear systems over the last two decades. For sparse linear systems, their application remains a challenge which has been studied by both the community of hierarchical matrices and the community of sparse matrices. On the one hand, the first step taken by the community of hierarchical matrices most often takes advantage of the sparsity of the problem through the use of nested dissection. While this approach benefits from the hierarchical structure, it is not, however, as efficient as sparse solvers regarding the exploitation of zeros and the structural separation of zeros from non-zeros. On the other hand, sparse factorization is organized so as to lead to a sequence of smaller dense operations, enticing sparse solvers to use this property and exploit compression techniques from hierarchical methods in order to reduce the computational cost of these elementary operations. Nonetheless, the globally hierarchical structure may be lost if the compression of hierarchical methods is used only locally on dense submatrices. We here review the main techniques that have been employed by both those communities, trying to highlight their common properties and their respective limits with a special emphasis on studies that have aimed to bridge the gap between them. With these observations in mind, we propose a class of hierarchical algorithms based on the symbolic analysis of the structure of the factors of a sparse matrix. These algorithms rely on a symbolic information to cluster and construct a hierarchical structure coherent with the non-zero pattern of the matrix. Moreover, the resulting hierarchical matrix relies on low-rank compression for the reduction of the memory consumption of large submatrices as well as the time to solution of the solver. We also compare multiple ordering techniques based on geometrical or topological properties. Finally, we open the discussion to a coupling between the Finite Element Method and the Boundary Element Method in a unified computational framework.

<p>This theses is dedicated to the study of generalized diagonal dominance and its<br />various beneflts. The starting point is the well known nonsingularity result of strictly diagonally dominant matrices, from which generalizations were formed in difierent directions. In theses, after a short overview of very well known results, special attention was turned to contemporary contributions, where overview of already published original material is given, together with new obtained results. Particulary, Ger&bull;sgorin-type localization theory for matrix pencils is developed, and application of the results in wireless sensor networks optimization problems is shown.</p> / <p><span class="fontstyle0">Ova teza je posvećena izučavanju generalizovane dijagonalne dominacije i njenih brojnih prednosti. Osnovu čini poznati rezultat o regularnosti strogo dijagonalnih matrica,<br />čija su uop&scaron;tenja formirana u brojnim pravcima. U tezi, nakon kratkog pregleda dobro poznatih rezultata, posebna pažnja je posvećena savremenim doprinosima, gde je dat i pregled već objavljenih autorovih rezultata, kao i detaljan tretman novih dobijenih rezultata. Posebno je razvijena teorija lokalizacije Ger&scaron;gorinovog tipa generalizovanih karakterističnih korena i pokazana je primena rezultata u problemima optimizacije bežičnih senzor mreža.</span></p>

<p>Predmet istraživanja u doktorskoj disertaciji je metoda za konstrukciju<br />lokalizacionih skupova za spektar i pseudospektar nelinearnih problema<br />karakterističnih korena bazirana na Geršgorinovoj teoremi i njenim<br />generalizacijama koja koristi osobine poznatih podklasa H-matrica.<br />Navedena tvrđenja i primeri rasvetljavaju odnose između navedenih<br />lokalizacionih skupova, što je posebno značajno za primenu u praksi.<br />Sadržaj ovog rada time predstavlja polaznu tačku za dublja istraživanja na<br />temu konstrukcije lokalizacionih skupova za spektar i pseudospektar<br />nelinearnih problema karakterističnih korena Geršgorinovog tipa.</p> / <p>The subject of research in the doctoral dissertation is a method for constructing<br />spectra and pseudospectra localization sets for nonlinear eigenvalue problems<br />based on Ger&scaron;gorin theorem and its generalizations, that uses the properties of<br />well-known subclasses of H-matrices. Theorems and examples given in this<br />paper are showing relations between stated localization sets, which is very<br />important for practical applications. Therefore, the content of this paper represent<br />the starting point for deeper explorations on the subject of constructing spectra<br />and pseudospectra localization sets for Ger&scaron;gorin type nonlinear eigenvalue<br />problems.</p>

<p>Ova doktorska disertacija izučava matrice zapisane u blok formi. Ona<br />sistematizuje postojeća i predstavlja nova tvrđenja o osobinama takvih matrica,<br />koja se baziraju na ideji generalizovane dijagonalne dominacije. Poznati<br />rezultati u tačkastom slučaju dobra su osnova za blok generalizacije, koje su<br />izvedene na dva različita načina, prvi zbog svoje jednostavnije primenljivosti,<br />a drugi zbog obuhvatanja šire klase matrica na koju se rezultati odnose.</p> / <p>This thesis is related to matrices written in their block form. It systematizes known and<br />represents new knowledge about properties of such matrices, which is based on the idea<br />of generalized diagonal dominance. Known results in the point case serve as a good basis<br />for block generalization, which is done in two different ways, the first one because of its<br />simple usability, and the other for capturing wider class of matrices which are treated.</p>

<p>The linear complementarity problems (LCP) arise from linear or quadratic programming, or from a variety of other particular application problems, like boundary problems, network equilibrium problems,contact problems, market equilibria problems, bimatrix games etc. Recently, many people have focused on the solver of LCP with a matrix having some kind of special property, for example, when this matrix is an H+-matrix, since this property is a sufficient condition for the existence and uniqueness of the soluition of LCP. Generally speaking, solving LCP can be approached from two essentially different perspectives. One of them includes the use of so-called direct methods, in the literature also known under the name pivoting methods. The other, and from our perspective - more interesting one, which we actually focus on in this thesis,<br />is the iterative approach. Among the vast collection of iterative solvers,our choice was one particular class of modulus based iterative methods.Since the subclass of modulus based-methods is again diverse in some sense, it can be specialized even further, by the introduction and the use of matrix splittings. The main goal of this thesis is to use the theory of H -matrices for proving convergence of the modulus-based multisplit-ting methods, and to use this new technique to analyze some important properties of iterative methods once the convergence has been guaranteed.</p> / <p>Problemi linearne komplementarnosti (LCP) se javljaju kod problema linearnog i kvadratnog programiranja i kod mnogih drugih problema iz prakse, kao &scaron;to su, na&nbsp; primer, problemi sa graničnim slojem, problemi mrežnih ekvilibrijuma, kontaktni problemi, problemi određivanja trži&scaron;ne ravnoteže, problemi bimatričnih igara i mnogi drugi. Ne tako davno, veliki broj autora se bavio razvijanjem postupaka za re&scaron;avanje LCP sa matricom koja ispunjava neko specijalno svojstvo, na primer, da pripada klasi H+-matrica, budući da je dobro poznato da je ovaj uslov dovoljan da obezbedi egzistenciju i jedinstvenost re&scaron;enja LCP. Uop&scaron;teno govoreći, re&scaron;avanju LCP moguce&nbsp; je pristupiti dvojako. Prvi pristup podrazumeva upotrebu takozvanih direktnih metoda, koje su u literaturi poznate i pod nazivom metode pivota. Drugoj kategoriji, koja je i sa stanovi&scaron;ta ove teze interesantna, pripadaju iterativni postupci. S obzirom da je ova kategorija izuzetno bogata, mi smo se opredelili za jednu od najznačajnijih varijanti, a&nbsp; to je modulski iterativni postupak. Međutim, ni ova odrednica nije dovoljno adekvatna, budući da modulski postupci obuhvataju nekolicinu različitih pravaca. Zato smo se odlučili da posmatramo postupke koji se zasnivaju na razlaganjima ali i vi&scaron;estrukim razlaganjima matrice. Glavni cilj ove doktorske disertacije jeste upotreba teorije H -matrica u teoremama o konvergenciji modulskih metoda zasnovanih na multisplitinzima matrice i kori&scaron;ćenje ove nove tehnike, sa ciljem analize bitnih osobina, nakon &scaron;to je konvergencija postupka zagarantovana.</p>

<p>This thesis studies subclasses of the class of H-matrices and their applications, with<br />emphasis on the investigation of the Schur complement properties. The contributions<br />of the thesis are new nonsingularity results, bounds for the maximum norm of the<br />inverse matrix, closure properties of some matrix classes under taking Schur<br />complements, as well as results on localization and separation of the eigenvalues of<br />the Schur complement based on the entries of the original matrix.</p> / <p>Докторска дисертација изучава поткласе класе Х-матрица и њихове примене,<br />првенствено у истраживању својстава Шуровог комплемента. Оригиналан допринос<br />тезе представљају нови услови за регуларност матрица, оцене максимум норме<br />инверзне матрице, резултати о затворености појединих класа матрица на Шуров<br />комплемент, као и резултати о локализацији и сепарацији карактеристичних<br />корена Шуровог комплемента на основу елемената полазне матрице.</p> / <p>Doktorska disertacija izučava potklase klase H-matrica i njihove primene,<br />prvenstveno u istraživanju svojstava Šurovog komplementa. Originalan doprinos<br />teze predstavljaju novi uslovi za regularnost matrica, ocene maksimum norme<br />inverzne matrice, rezultati o zatvorenosti pojedinih klasa matrica na Šurov<br />komplement, kao i rezultati o lokalizaciji i separaciji karakterističnih<br />korena Šurovog komplementa na osnovu elemenata polazne matrice.</p>