diplomsko delo
Matjaž Ciglič (Author), Aljaž Zalar (Mentor)

Abstract

Problem matričnih napolnitev sprašuje po lastnostih matrik, dobljenih iz delno napolnjenih matrik, pri čemer manjkajoče vhode poljubno izberemo. Problem se pojavlja na številnih področjih, kot so problemi momentov, realna algebraična geometrija, študij velikih podatkov, itd. V diplomskem delu se osredotočimo na študij možnih inercij napolnitev posebnih hermitskih matrik. Z uporabo orodij linearne algebre pokažemo, da lahko vse možne inercije parametriziramo s celoštevilskimi točkami znotraj inercijskega politopa. Predstavimo tudi povezavo posebnih matrik s tetivnimi grafi in prek nje izpeljemo formulo za cenejši izračun inercije matrike. Algoritme za izračun inercijskega politopa in inercije matrik posebne oblike tudi implementiramo in delovanje prikažemo na numeričnih primerih.

Keywords

matrične napolnitve;hermitske matrike;inercija matrik;lastne vrednosti;inercijski politop;tetivni grafi;drevesa klik;popolna eliminacijska ureditev;univerzitetni študij;diplomske naloge;

Data

Language: Slovenian
Year of publishing:
Typology: 2.11 - Undergraduate Thesis
Organization: UL FRI - Faculty of Computer and Information Science
Publisher: [M. Ciglič]
UDC: 004:51(043.2)
COBISS: 116096003 Link will open in a new window
Views: 85
Downloads: 25
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: Inertia of matrix completions
Secondary abstract: The matrix completion problem asks to describe the properties of matrices, obtained as completions of given matrices with some missing entries. The problem is important due to its applications in many areas, such as moment problems, real algebraic geometry, big data analysis, etc. In the diploma thesis we focus on the study of possible inertia of completions of special hermitian matrices. Using tools from linear algebra we show, that all possible inertia are parametrized by the integer points within the inertia polytope. We present the connection between special matrices and chordal graphs and use it to derive a formula for more efficient computation of inertia. We also implement the algorithms for the computation of the inertia polytope and the inertia of special matrices and present them on numerical examples.
Secondary keywords: matrix completions;hermitian matrices;matrix inertia;eigenvalues;inertia polytope;chordal graphs;clique trees;perfect elimination ordering;computer science;diploma;Matrike (matematika);Računalništvo;Univerzitetna in visokošolska dela;
Type (COBISS): Bachelor thesis/paper
Study programme: 1000468
Thesis comment: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages: 60 str.
ID: 15956592