Narrow your search
Listing 1 - 10 of 24 << page
of 3
>>
Sort by

Multi
Diagonal-plus-semiseparable matrices and their use in numerical linear algebra.
Authors: --- --- ---
ISBN: 9056825992 Year: 2005 Publisher: Leuven K.U.Leuven. Faculteit Ingenieurswetenschappen

Loading...
Export citation

Choose an application

Bookmark

Abstract

Gestructureerde matrices zijn zeer belangrijk in lineaire algebra omdat ze minder geheugenplaats innemen dan algemene matrices en omdat bewerkingen met deze matrices minder rekenwerk vergen dan wanneer volle, niet-gestructureerde matrices gebruikt worden. Diagonaal-plus-semiseparabele matrices vormen een klasse van zulke gestructureerde matrices. In dit proefschrift zoeken we naar een geschikte definitie voor deze klasse van matrices en een bijpassende voorstelling.Ook andere definities die in de literatuur gebruikt worden, worden belicht en de studie van diagonaal-plus-semiseparabele matrices wordt gemotiveerd. In een eerste deel construeren we een reductie algoritme dat elke symmetrische matrix omzet in een overeenkomstige diagonaal-plus-semiseparabele matrix. Dit algoritme heeft het Lanczos-Ritz convergentiegedrag en in elke stap wordt er een geneste deelruimte iteratie uitgevoerd. Deel 2 belicht twee basisproblemen uit numerieke lineaire algebra: het oplossen van lineaire systemen en het symmetrisch eigenwaardeprobleem. Eerst construeren we twee snelle algoritmes om diagonaal-plus-semiseparabele lineaire systemen op te lossen. Daarna besprekenwe drie verschillende technieken die gebruikt worden om het symmetrisch eigenwaardeprobleem op te lossen voor diagonaal-plus-semiseparabele matrices: een impliciet QR-algoritme, drie verschillende verdeel-en-heers algoritmes en een Cholesky-LR-algoritme. Het laatste algoritme is enkel toepasbaar op symmetrische, positief definiete diagonaal-plus-semiseparabele matrices. In het laatste deel introduceren we twee hogere rang uitbreidingen van semiseparabele matrices samen met een bijpassende voorstelling. Elke symmetrische matrix kan omgezet worden in een overeenkomstige hogere rang semiseparabele matrix en deze omzetting heeft het blok-Lanczos-Ritz convergentiegedrag gecombineerd met een soort van geneste deelruimte iteratie in elke stap. Numerieke experimenten zijn toegevoegd en de programma's zijn ter beschikking gesteld op het internet. In linear algebra structured matrices are of great interest because they consume less storage than arbitrary matrices and the computational cost of algorithms involving structured matrices is less than for dense, non-structured ones. Several problems can also be translated into similar problems with structured matrices. Diagonal-plus-semiseparable matrices form a class of such structured matrices. First we look for a suitable definition of this class of matrices and a corresponding representation. Other definitions used in the literature are discussed and the study of diagonal-plus-semiseparable matrices is motivated. In Part I of this thesis a reduction algorithm that transforms any symmetric matrix into a similar diagonal-plus-semiseparable one is presented which has a Lanczos-Ritz convergence behavior and performs a kind of nested subspace iteration at each step. It has the advantage that the diagonal can be chosen freely. Part II focuses on two basic problems in numerical linear algebra: the solution of linear systems and the symmetric eigenvalue problem. First, two fast algorithms for solving diagonal-plus-semiseparable linear systems are constructed. Next, three different techniques for solving the symmetric eigenvalue problem of diagonal-plus-semiseparable matrices are presented: an implicit QR-algorithm, three different divide-and-conquer algorithms and a Cholesky-LR-algorithm. The latter is onlyapplicable when the symmetric diagonal-plus-semiseparable matrix is positive definite. In a last part we introduce two higher rank extensions of semiseparable matrices together with a suitable representation. Any symmetric matrix can be transformed into a similar higher-order semiseparable one and this reduction algorithm has a block-Lanczos-Ritz behavior combined with a kind of nested subspace iteration at each step. Numerical experiments are included and the software is made freely available on the internet. Twee fundamentele problemen uit de numerieke lineaire algebra zijn het oplossen van stelsels lineaire vergelijkingen en van eigenwaardeproblemen. Deze problemen zijn vaak een belangrijk onderdeel in toepassingen zoals, bijvoorbeeld bij de zoekrobot Google en in beeldcompressie. Een vaak gebruikte techniek voor het oplossen van bovenvermelde problemen is gebaseerd op tridiagonale matrices. In dit proefschrift wordt een alternatieve manier voorgesteld die gebruik maakt van diagonaal-plus-semiseparabele matrices en die enkele bijkomende voordelen biedt. De eigenschappen van deze diagonaal-plus-semiseparabele matrices zijn in detail bestudeerd. Snelle en stabiele algoritmes voor het oplossen van stelsels lineaire vergelijkingen en eigenwaardeproblemen, specifiek voor deze matrices, zijn voorgesteld.


Multi
Regularization techniques in model fitting and parameter estimation.

Loading...
Export citation

Choose an application

Bookmark

Abstract

Klassieke methoden voor de behandeling van rekenkundige problemen kunnen mislopen in het geval van ``ill-posed'' problemen. Datamodellering met lineaire en niet-lineaire modellen is voor dit speciale geval bestudeerd in dit proefschrift. In het lineaire geval, bekijken we het totaal kleinste kwadraten probleem. Er bestaan speciale methoden die ontwikkeld zijn voor het zogenaamde niet-generische geval. Die breiden we uit naar het geval van bijna-niet-generische problemen. Meerdere methoden van regularisatie voor het totaal kleinste kwadraten probleem zijn geanalyseerd. Ze zijn gebaseerd op afknottechnieken of op bestraffingsoptimalisatie. Het is mogelijk dat de oplossingen van onze nieuwe problemen geen gesloten formules hebben. Daarom bespreken we lineaire algebra en lokale optimalisatie technieken. Datamodellering met niet-lineaire modellen is het onderwerp van de tweede deel van het proefschrift. We breiden de niet-lineaire regressietheorie uit tot twee gevallen: het eerste geval waarbij aanvullende regulariserende voorwaarden nodig zijn, en het tweede geval van een semiparametrische context waarbij een deel van het model als bekend beschouwd wordt, maar een andere deel als onbekend beschouwd wordt. Deze theorie kan in de biomedische wereld toegepast worden voor de kwantificatie van metabolieten in de hersens uit magnetische resonantie spectroscopische signalen. We consider fitting data by linear and nonlinear models. The specific problems that we aim at, although they encompass classical formulations, have as common ground the fact that we attack a special situation: the ill-posed problems. In the linear case, we consider the total least squares problem. There exist special methods to approach the so-called nongeneric cases, but we propose extensions for the more commonly encountered close-to-nongeneric problems. Several methods of introducing regularization in the context of total least squares are analyzed. They are based on truncation methods or on penalty optimization. The obtained problems might not have closed form solutions. We discuss numerical linear algebra and local optimization methods. Data fitting by nonlinear or nonparametric models is the second subject of the thesis. We extend the nonlinear regression theory to the case when we have to deal with supplementary regularization constraints, and to a semiparametric context, where only part of the model is known and we have to take into account a component with unknown formulation. We apply the developed theory to the biomedical application of quantifying metabolite concentrations in the human brain from nuclear magnetic resonance spectroscopic signals. Als een computer rekent, kunnen verschillende numerieke problemen gebeuren als gevolg van afrondingsfouten of van de wiskundige vereenvoudiging en benadering van een reeel, fysisch model. We bestuderen een klasse van wiskundige modellen waarbij dit effect het meest hinderlijke is; die problemen worden ``ill-posed'' genoemd. We formuleren meerdere nieuwe technieken en verbeterde algoritmen voor ill-posed problemen in lineaire en niet-lineaire contexten. We passen onze methoden toe op de kwantificatie van scheikundige stoffen in de hersens uit magnetische resonantie spectroscopische signalen. When numerical computations are performed, problems might arise due to the finite precision arithmetic of the computer or due to mathematical approximations and simplifications of the real physical models. We study a class of mathematical problems where this effect is the most troublesome; these problems are rightfully called ill-posed. We formulate several new approaches and improved algorithms to deal with ill-posed problems in linear and nonlinear modeling contexts. We apply our formulations to a biomedical problem of quantifying the concentrations of chemical substances in the human brain, using magnetic resonance spectroscopy data.


Multi
Rank Structured Matrices.

Loading...
Export citation

Choose an application

Bookmark

Abstract

Ranggestructureerde matrices. Veel praktische problemen in de ingenieurswetenschappen kunnen geformuleerd worden met behulp van lineaire algebra en matrices. Vaak zullen deze matrices een bepaalde structuur hebben die voortkomt uit de aard van het probleem. Om het oplossen van deze problemen op een efficiënte manier te laten gebeuren, zal men dan proberen om zoveel mogelijk gebruik te maken van de structuur van de bijhorende matrices. Een structuur die in de praktijk vaak voorkomt is de ijlheid van de matrix, wat betekent dat de matrix slechts een relatief klein aantal elementen heeft die verschillend zijn van nul. Een ruimere klasse van gestructureerde matrices zijn degene die we ranggestructureerd noemen. Dit betekent ruwweg dat de matrix veel submatrices van lage rang heeft. In deze thesis bestuderen we het gedrag van ranggestructureerde matrices onder verscheidene operaties: het QR-algoritme, matrix-inversie en Schur-complementatie. We tonen aan dat er in alle gevallen behoud is van structuur. Vervolgens tonen we aan hoe dit behoud van structuur gebruikt kan worden om snelle en efficiënte algoritmen te ontwikkelen voor ranggestructureerde matrices, bijvoorbeeld voor het oplossen van een stelsel van lineaire vergelijkingen, of voor het berekenen van de eigenwaarden. Tenslotte tonen we ook aan hoe rangstructuren gerelateerd zijn met de snelle Fouriertransformatie (Fast Fourier transform, FFT).

Stochastic local search : foundations and applications
Authors: ---
ISBN: 9781558608726 1558608729 1493303732 9786611015053 1281015059 0080498248 9780080498249 9781281015051 6611015051 Year: 2005 Publisher: San Francisco : Elsevier ; Morgan Kaufmann publishers,

Loading...
Export citation

Choose an application

Bookmark

Abstract

Stochastic local search (SLS) algorithms are among the most prominent and successful techniques for solving computationally difficult problems in many areas of computer science and operations research, including propositional satisfiability, constraint satisfaction, routing, and scheduling. SLS algorithms have also become increasingly popular for solving challenging combinatorial problems in many application areas, such as e-commerce and bioinformatics.Hoos and Stützle offer the first systematic and unified treatment of SLS algorithms. In this groundbreaking new book, they examine the


Multi
Point cloud processing using linear algebra and graph theory.

Loading...
Export citation

Choose an application

Bookmark

Abstract

Moderne 3D scanners maken het mogelijk om heel snel grote hoeveelheden 3D data te genereren. Dit resulteert in een steeds groeiend aantal toepassingen, gaande van digitalisatie van historische objecten tot gezichtsauthenticatie. In deze thesis stellen we een aantal nieuwe algoritmen voor om de data, verkregen met behulp van een 3D scanner, te verwerken. Deze data worden een puntenwolk genoemd en bestaan uit een verzameling punten bemonsterd van het 3D oppervlak van een object. De voorgestelde algoritmen betreffen enkele fundamentele topics in puntenwolkverwerking: triangulatie, vereffening en randbepaling. We analyseren de algoritmen vanuit het standpunt van efficiëntie, praktische toepasbaarheid en de volledigheid van de onderliggende theorie. Randbepaling is een veel voorkomend probleem in toepassingen waar het nodig is om te weten waar de gaten en externe randen liggen in een puntenwolk. In dit werk ontwikkelen we een nieuw algoritme voor het bepalen van randen, die we als gesloten, veelhoekige randlussen voorstellen. Het resultaat van dit algoritme wordt verder gebruikt door de andere algoritmen besproken in de thesis. Een andere fundamentele operatie is de triangulatie van puntenwolken. Het resultaat van deze operatie is een driehoekig rooster dat de buurpunten op een consistente manier met elkaar verbindt en zo de connectiviteitsinformatie toevoegt aan de puntenwolk. Wij bespreken twee aanpakken voor het trianguleren van puntenwolken. De eerste aanpak is gebaseerd op de zogenaamde roosterloze parameterisatietechniek en de tweede aanpak wordt het volumetrisch projectie-algoritme genoemd en steunt op de volumetrische voorstelling van de puntenwolk. Elke aanpak heeft zijn voor- en nadelen en kan verschillende soorten input-puntenwolken behandelen. Roosterloze parameterisatie is geschikt voor puntenwolken met schijftopologie en het volumetrisch projectie-algoritme is toepasbaar op gesloten puntenwolken van willekeurige genus en zonder randen. Vereffening is een frequent gebruikte operatie. Het is nodig om de ruis in opgemeten puntenwolken te verwijderen en op die manier de verdere verwerking gemakkelijker te maken. In het laatste deel van deze thesis stellen wij een nieuw vereffeningsalgoritme voor, dat geformuleerd wordt als een lineaire algebra optimalisatieprobleem met beperkingen. Één van de voordelen van het algoritme is zijn algemeenheid, in de zin dat het niet alleen op puntenwolken toegepast kan worden, maar ook op triangulaties, grafieken, curvenetwerken en in het algemeen op functies gedefinieerd in de knopen van een grafe. Het algoritme steunt op een efficiënte kleinste-kwadratensolver en heeft gegarandeerde convergentie. Bovendien heeft het algoritme interessante theoretische eigenschappen, wegens zijn verwantschap met de geometrie-bewuste basissen en Tikhonov-regularisatie. De gepresenteerde algoritmen dragen bij tot het domein van digital geometry processing en trachten de vraag naar efficiënte puntenwolkverwerkingsalgoritmen te beantwoorden. Modern 3D scanners make it possible to collect large amounts of 3D data in just a few seconds. This technological progress results in a growing number of applications ranging from the digitalization of historical artifacts to facial authentication. In this thesis we propose a number of novel algorithms for the processing of data obtained using 3D scanners. Such data is called a point cloud and it consists of a collection of points sampled from the surface of a 3D object. The proposed algorithms address some fundamental topics in point cloud processing, i.e. triangulation, smoothing and boundary extraction. We analyze the algorithms from the viewpoint of efficiency, practicality and the soundness of the underlying theory. Boundary extraction is required in many applications, where it is useful to know where the holes and exterior boundaries of the point cloud are situated. Using concepts from graph theory we develop a novel algorithm for the extraction of closed polygonal boundary loops in point clouds. This boundary information is used by other algorithms discussed in this thesis. Another fundamental operation, often performed on point clouds, is triangulation. The result of this operation is a triangular mesh, which connects the neighboring points with each other in a consistent way, thereby adding connectivity information to the point cloud. We discuss two approaches for triangulating point clouds. One is based on the so-called meshless parameterization technique and the other is called volumetric snapping and relies on a volumetric representation of the point data. Each approach has its advantages and can handle different types of input point clouds. Meshless parameterization is suitable for point clouds with disc topology and the volumetric snapping algorithm handles closed point clouds of arbitrary genus without boundaries. Smoothing is a frequently used operation on point clouds. It is required to remove noise and to make further processing easier. In the last part of the thesis we propose a new smoothing algorithm, which is formulated as a constrained linear algebra optimization problem. The advantage of the algorithm is its generality, in the sense that it can be applied not only to point clouds, but also to triangulations, plots, curve networks and in general to functions defined on graphs. The algorithm relies on an efficient least squares solver and has guaranteed convergence. Furthermore, it possesses interesting theoretical properties, because of its connection with the geometry-aware bases and Tikhonov regularization. The presented algorithms contribute to the new field of digital geometry processing and help to address the demand for efficient point cloud processing techniques. Moderne 3D scanners maken het mogelijk om heel snel grote hoeveelheden 3D data te genereren. Dit resulteert in een steeds groeiend aantal toepassingen, gaande van digitalisatie van historische objecten tot gezichtsauthenticatie. In veel gevallen is het resultaat van een scan een puntenwolk, ofwel een verzameling punten die het oppervlak van het object voorstellen. In alle toepassingen die met puntenwolken te maken hebben is het noodzakelijk om de grote hoeveelheden punten op een efficiënte manier te verwerken. Een van de veelvoorkomende operaties is bijvoorbeeld de triangulatie van een puntenwolk, waarbij een driehoekig rooster wordt opgesteld bestaande uit driehoekige facetten. Zo een triangulatie is een handige voorstelling van het object, omdat het topologische informatie bevat (zoals gaten en randen) en is gemakkelijk om mee te werken. In deze thesis trachten we de vraag naar puntenwolkverwerkingstechnieken te beantwoorden en stellen een aantal nieuwe algoritmen voor. In het bijzonder behandelen we enkele fundamentele topics in puntenwolkverwerking: triangulatie, vereffening en randbepaling. We analyseren de algoritmen vanuit het standpunt van efficiëntie, praktische toepasbaarheid en de volledigheid van de onderliggende theorie.


Book
Listing 1 - 10 of 24 << page
of 3
>>
Sort by