La résolution de problèmes d’onde par une méthode d’éléments finis de frontière (BEM) conduit à des systèmes d’équations linéaires pleins dont la taille augmente très vite pour les applications pratiques. Il est alors impératif d’employer des méthodes de résolution dites rapides. La méthode des multipôles rapides (FMM) accélère la résolution de ces systèmes par des algorithmes itératifs. La méthode des H-matrices permet d’accélérer les solveurs directs nécessaires aux cas d’application massivement multi-seconds membres. Elle a été introduite et théoriquement justifiée dans le cas de l’équation de Laplace.Néanmoins elle s’avère performante au-delà de ce qui est attendu pour des problèmes d’onde relativement haute fréquence. L’objectif de cette thèse est de comprendre pourquoi la méthode fonctionne et proposer des améliorations pour des fréquences plus élevées.Une H-matrice est une représentation hiérarchique par arbre permettant un stockage compressé des données grâce à une séparation des interactions proches (ou singulières)et lointaines (dites admissibles). Un bloc admissible a une représentation de rang faible de type UVT tandis que les interactions singulières sont représentées par des blocs pleins de petites tailles. Cette méthode permet une approximation rapide d’une matrice BEM par une H-matrice ainsi qu’une méthode de factorisation rapide de type Cholesky dont les facteurs sont également de type H-matrice.Nous montrons la nécessité d’un critère d’admissibilité dépendant de la fréquence et introduisons un critère dit de Fresnel basé sur la zone de diffraction de Fresnel. Ceci permet de contrôler la croissance du rang d’un bloc et nous proposons une estimation précise de celui-ci à haute fréquence à partir de résultats sur les fonctions d’onde sphéroïdales.Nous en déduisons une méthode de type HCA-II, robuste et fiable, d’assemblage rapide compressé à la précision voulue.Nous étudions les propriétés de cet algorithme en fonction de divers paramètres et leur influence sur le contrôle et la croissance du rang en fonction de la fréquence.Nous introduisons la notion de section efficace d’interaction entre deux clusters vérifiant le critère de Fresnel. Si celle-ci n’est pas dégénérée, le rang du bloc croît au plus linéairement avec la fréquence ; pour une interaction entre deux clusters coplanaires nous montrons une croissance comme la racine carrée de la fréquence. Ces développements sont illustrés sur des maillages représentatifs des interactions à haute fréquence. / The boundary elements method (BEM) leads to dense linear systemswhose size growsrapidly in pratice ; hence the use of so-called fast methods. The fast multipole method(FMM) accelerates the resolution of BEM systems within an iterative scheme. The H-matrix method speeds up a direct resolution which is needed in massively multiple righthandsides problems. It has been provably introduced in the context of the Laplace equation.However, the use ofH-matrices for relatively high-frequency wave problems leadsto results above expectations. This thesis main goal is to provide an explanation of thesegood results and thus improve the method for higher frequencies.A H-matrix is a compressed tree-based hierarchical representation of the data associated with an admissibility criterion to separate the near (or singular) and far (or compres-sed) fields. An admissible block reads as a UVT rank deficient matrix while the singularblocks are dense with small dimensions. BEM matrices are efficiently represented byH-matrices and this method also allows for a fast Cholesky factorization whose factors arealsoH-matrices.Our work on the admissibility condition emphasizes the necessity of a frequency dependantadmissibility criterion. This new criterion is based on the Fresnel diffraction areathus labelled Fresnel admissibility condition. In that case a precise estimation of the rankof a high-frequency block is proposed thanks to the spheroidal wave functions theory.Consequently, a robust and reliable HCA-II type algorithm has been developed to ensurea compressed precision-controlled assembly. The influence of various parameters on thisnew algorithm behaviour is discussed ; in particular their influence on the control andthe growth of the rank according to the frequency.We define the interaction cross sectionfor two Fresnel-admissible clusters and show in the non-degenerate case that the rankgrowth is linear according to the frequency in the high-frequency regime ; interaction ofcoplanar clusters results in growth like the square root of the frequency. All these resultsare presented on meshes adapted to high-frequency interactions.

<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>