Spelling suggestions: "subject:"amatrices"" "subject:"2matrices""
1 |
Determinación y propiedades de H-matricesScott Guilleard, José Antonio 14 December 2015 (has links)
[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
|
2 |
Bridging the Gap Between H-Matrices and Sparse Direct Methods for the Solution of Large Linear Systems / Combler l’écart entre H-Matrices et méthodes directes creuses pour la résolution de systèmes linéaires de grandes taillesFalco, Aurélien 24 June 2019 (has links)
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.
|
3 |
Benefits from the generalized diagonal dominance / Prednosti generalizovane dijagonalne dominacijeKostić Vladimir 03 July 2010 (has links)
<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•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š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šgorinovog tipa generalizovanih karakterističnih korena i pokazana je primena rezultata u problemima optimizacije bežičnih senzor mreža.</span></p>
|
4 |
Lokalizacije Geršgorinovog tipa za nelinearne probleme karakterističnih korena / Geršgorin-type localizations for Nonlinear Eigenvalue ProblemsGardašević Dragana 21 February 2019 (has links)
<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š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šgorin type nonlinear eigenvalue<br />problems.</p>
|
5 |
Generalizovana dijagonalna dominacija za blok matrice i mogućnosti njene primene / Generalized diagonal dominance for block matrices and possibilites of its applicationDoroslovački Ksenija 06 May 2014 (has links)
<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>
|
6 |
Convergence Analysis of Modulus Based Methods for Linear Complementarity Problems / Analiza konvergencije modulus metoda za probleme linearne komplementarnostiSaeed Aboglida Saeed Abear 18 March 2019 (has links)
<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 što su, na primer, problemi sa graničnim slojem, problemi mrežnih ekvilibrijuma, kontaktni problemi, problemi određivanja tržišne ravnoteže, problemi bimatričnih igara i mnogi drugi. Ne tako davno, veliki broj autora se bavio razvijanjem postupaka za reš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šenja LCP. Uopšteno govoreći, rešavanju LCP moguce 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š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 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š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šćenje ove nove tehnike, sa ciljem analize bitnih osobina, nakon što je konvergencija postupka zagarantovana.</p>
|
7 |
The Schur complement and H-matrix theory / Шуров комплемент и теорија Х-матрица / Šurov komplement i teorija H-matricaNedović Maja 19 October 2016 (has links)
<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>
|
Page generated in 0.0273 seconds