Het inverteerbaar maken van matrices (Restricted Invertibility)

Bachelor thesis (2012)

Authors

Contributors

F. Valentin (mentor)
M. Veraar (mentor)
Department
Applied mathematics (EEMCS) (TU Delft)
Copyright: © 2012 Wildeboer, M.E.
More Info
expand_more

Published Date

13-07-2012

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Applied mathematics

Abstract

Matrices zijn objecten die vrij centraal staan in de studie der wiskunde. Ze worden gebruikt om data te representeren, zoals grafen en stelsels van lineaire vergelijkingen. Soms kan het handig zijn om zo'n willekeurige matrix te kunnen benaderen met een 'schaarse' of 'gestructureerde' matrix. Nadruk ligt hierbij op het feit dat de benadering zinvol moet zijn en er dus extra eisen aan deze benadering worden gesteld. De meest zinvolle benadering hiervoor is in 2010 gegeven door Daniel Spielman en Nikhil Srivastava, onder andere toegepast op grafen. In grafentheorie komt dit resultaat min of meer overeen met het Er wordt uitgelegd hoe Spielman en Srivastava een zinvolle benadering van zo'n matrix vonden. Daarnaast wordt er een computeralgortime gepresenteerd die als output die zinvolle matrix heeft. Als laatste wordt dit algoritme toegepast op een aantal matrices ter demonstratie.