<!--{{{-->
<link rel='alternate' type='application/rss+xml' title='RSS' href='index.xml' />
<!--}}}-->
Background: #fff
Foreground: #000
PrimaryPale: #8cf
PrimaryLight: #18f
PrimaryMid: #04b
PrimaryDark: #014
SecondaryPale: #ffc
SecondaryLight: #fe8
SecondaryMid: #db4
SecondaryDark: #841
TertiaryPale: #eee
TertiaryLight: #ccc
TertiaryMid: #999
TertiaryDark: #666
Error: #f88
/*{{{*/
body {background:[[ColorPalette::Background]]; color:[[ColorPalette::Foreground]];}

a {color:[[ColorPalette::PrimaryMid]];}
a:hover {background-color:[[ColorPalette::PrimaryMid]]; color:[[ColorPalette::Background]];}
a img {border:0;}

h1,h2,h3,h4,h5,h6 {color:[[ColorPalette::SecondaryDark]]; background:transparent;}
h1 {border-bottom:2px solid [[ColorPalette::TertiaryLight]];}
h2,h3 {border-bottom:1px solid [[ColorPalette::TertiaryLight]];}

.button {color:[[ColorPalette::PrimaryDark]]; border:1px solid [[ColorPalette::Background]];}
.button:hover {color:[[ColorPalette::PrimaryDark]]; background:[[ColorPalette::SecondaryLight]]; border-color:[[ColorPalette::SecondaryMid]];}
.button:active {color:[[ColorPalette::Background]]; background:[[ColorPalette::SecondaryMid]]; border:1px solid [[ColorPalette::SecondaryDark]];}

.header {background:[[ColorPalette::PrimaryMid]];}
.headerShadow {color:[[ColorPalette::Foreground]];}
.headerShadow a {font-weight:normal; color:[[ColorPalette::Foreground]];}
.headerForeground {color:[[ColorPalette::Background]];}
.headerForeground a {font-weight:normal; color:[[ColorPalette::PrimaryPale]];}

.tabSelected{color:[[ColorPalette::PrimaryDark]];
	background:[[ColorPalette::TertiaryPale]];
	border-left:1px solid [[ColorPalette::TertiaryLight]];
	border-top:1px solid [[ColorPalette::TertiaryLight]];
	border-right:1px solid [[ColorPalette::TertiaryLight]];
}
.tabUnselected {color:[[ColorPalette::Background]]; background:[[ColorPalette::TertiaryMid]];}
.tabContents {color:[[ColorPalette::PrimaryDark]]; background:[[ColorPalette::TertiaryPale]]; border:1px solid [[ColorPalette::TertiaryLight]];}
.tabContents .button {border:0;}

#sidebar {}
#sidebarOptions input {border:1px solid [[ColorPalette::PrimaryMid]];}
#sidebarOptions .sliderPanel {background:[[ColorPalette::PrimaryPale]];}
#sidebarOptions .sliderPanel a {border:none;color:[[ColorPalette::PrimaryMid]];}
#sidebarOptions .sliderPanel a:hover {color:[[ColorPalette::Background]]; background:[[ColorPalette::PrimaryMid]];}
#sidebarOptions .sliderPanel a:active {color:[[ColorPalette::PrimaryMid]]; background:[[ColorPalette::Background]];}

.wizard {background:[[ColorPalette::PrimaryPale]]; border:1px solid [[ColorPalette::PrimaryMid]];}
.wizard h1 {color:[[ColorPalette::PrimaryDark]]; border:none;}
.wizard h2 {color:[[ColorPalette::Foreground]]; border:none;}
.wizardStep {background:[[ColorPalette::Background]]; color:[[ColorPalette::Foreground]];
	border:1px solid [[ColorPalette::PrimaryMid]];}
.wizardStep.wizardStepDone {background:[[ColorPalette::TertiaryLight]];}
.wizardFooter {background:[[ColorPalette::PrimaryPale]];}
.wizardFooter .status {background:[[ColorPalette::PrimaryDark]]; color:[[ColorPalette::Background]];}
.wizard .button {color:[[ColorPalette::Foreground]]; background:[[ColorPalette::SecondaryLight]]; border: 1px solid;
	border-color:[[ColorPalette::SecondaryPale]] [[ColorPalette::SecondaryDark]] [[ColorPalette::SecondaryDark]] [[ColorPalette::SecondaryPale]];}
.wizard .button:hover {color:[[ColorPalette::Foreground]]; background:[[ColorPalette::Background]];}
.wizard .button:active {color:[[ColorPalette::Background]]; background:[[ColorPalette::Foreground]]; border: 1px solid;
	border-color:[[ColorPalette::PrimaryDark]] [[ColorPalette::PrimaryPale]] [[ColorPalette::PrimaryPale]] [[ColorPalette::PrimaryDark]];}

.wizard .notChanged {background:transparent;}
.wizard .changedLocally {background:#80ff80;}
.wizard .changedServer {background:#8080ff;}
.wizard .changedBoth {background:#ff8080;}
.wizard .notFound {background:#ffff80;}
.wizard .putToServer {background:#ff80ff;}
.wizard .gotFromServer {background:#80ffff;}

#messageArea {border:1px solid [[ColorPalette::SecondaryMid]]; background:[[ColorPalette::SecondaryLight]]; color:[[ColorPalette::Foreground]];}
#messageArea .button {color:[[ColorPalette::PrimaryMid]]; background:[[ColorPalette::SecondaryPale]]; border:none;}

.popupTiddler {background:[[ColorPalette::TertiaryPale]]; border:2px solid [[ColorPalette::TertiaryMid]];}

.popup {background:[[ColorPalette::TertiaryPale]]; color:[[ColorPalette::TertiaryDark]]; border-left:1px solid [[ColorPalette::TertiaryMid]]; border-top:1px solid [[ColorPalette::TertiaryMid]]; border-right:2px solid [[ColorPalette::TertiaryDark]]; border-bottom:2px solid [[ColorPalette::TertiaryDark]];}
.popup hr {color:[[ColorPalette::PrimaryDark]]; background:[[ColorPalette::PrimaryDark]]; border-bottom:1px;}
.popup li.disabled {color:[[ColorPalette::TertiaryMid]];}
.popup li a, .popup li a:visited {color:[[ColorPalette::Foreground]]; border: none;}
.popup li a:hover {background:[[ColorPalette::SecondaryLight]]; color:[[ColorPalette::Foreground]]; border: none;}
.popup li a:active {background:[[ColorPalette::SecondaryPale]]; color:[[ColorPalette::Foreground]]; border: none;}
.popupHighlight {background:[[ColorPalette::Background]]; color:[[ColorPalette::Foreground]];}
.listBreak div {border-bottom:1px solid [[ColorPalette::TertiaryDark]];}

.tiddler .defaultCommand {font-weight:bold;}

.shadow .title {color:[[ColorPalette::TertiaryDark]];}

.title {color:[[ColorPalette::SecondaryDark]];}
.subtitle {color:[[ColorPalette::TertiaryDark]];}

.toolbar {color:[[ColorPalette::PrimaryMid]];}
.toolbar a {color:[[ColorPalette::TertiaryLight]];}
.selected .toolbar a {color:[[ColorPalette::TertiaryMid]];}
.selected .toolbar a:hover {color:[[ColorPalette::Foreground]];}

.tagging, .tagged {border:1px solid [[ColorPalette::TertiaryPale]]; background-color:[[ColorPalette::TertiaryPale]];}
.selected .tagging, .selected .tagged {background-color:[[ColorPalette::TertiaryLight]]; border:1px solid [[ColorPalette::TertiaryMid]];}
.tagging .listTitle, .tagged .listTitle {color:[[ColorPalette::PrimaryDark]];}
.tagging .button, .tagged .button {border:none;}

.footer {color:[[ColorPalette::TertiaryLight]];}
.selected .footer {color:[[ColorPalette::TertiaryMid]];}

.sparkline {background:[[ColorPalette::PrimaryPale]]; border:0;}
.sparktick {background:[[ColorPalette::PrimaryDark]];}

.error, .errorButton {color:[[ColorPalette::Foreground]]; background:[[ColorPalette::Error]];}
.warning {color:[[ColorPalette::Foreground]]; background:[[ColorPalette::SecondaryPale]];}
.lowlight {background:[[ColorPalette::TertiaryLight]];}

.zoomer {background:none; color:[[ColorPalette::TertiaryMid]]; border:3px solid [[ColorPalette::TertiaryMid]];}

.imageLink, #displayArea .imageLink {background:transparent;}

.annotation {background:[[ColorPalette::SecondaryLight]]; color:[[ColorPalette::Foreground]]; border:2px solid [[ColorPalette::SecondaryMid]];}

.viewer .listTitle {list-style-type:none; margin-left:-2em;}
.viewer .button {border:1px solid [[ColorPalette::SecondaryMid]];}
.viewer blockquote {border-left:3px solid [[ColorPalette::TertiaryDark]];}

.viewer table, table.twtable {border:2px solid [[ColorPalette::TertiaryDark]];}
.viewer th, .viewer thead td, .twtable th, .twtable thead td {background:[[ColorPalette::SecondaryMid]]; border:1px solid [[ColorPalette::TertiaryDark]]; color:[[ColorPalette::Background]];}
.viewer td, .viewer tr, .twtable td, .twtable tr {border:1px solid [[ColorPalette::TertiaryDark]];}

.viewer pre {border:1px solid [[ColorPalette::SecondaryLight]]; background:[[ColorPalette::SecondaryPale]];}
.viewer code {color:[[ColorPalette::SecondaryDark]];}
.viewer hr {border:0; border-top:dashed 1px [[ColorPalette::TertiaryDark]]; color:[[ColorPalette::TertiaryDark]];}

.highlight, .marked {background:[[ColorPalette::SecondaryLight]];}

.editor input {border:1px solid [[ColorPalette::PrimaryMid]];}
.editor textarea {border:1px solid [[ColorPalette::PrimaryMid]]; width:100%;}
.editorFooter {color:[[ColorPalette::TertiaryMid]];}
.readOnly {background:[[ColorPalette::TertiaryPale]];}

#backstageArea {background:[[ColorPalette::Foreground]]; color:[[ColorPalette::TertiaryMid]];}
#backstageArea a {background:[[ColorPalette::Foreground]]; color:[[ColorPalette::Background]]; border:none;}
#backstageArea a:hover {background:[[ColorPalette::SecondaryLight]]; color:[[ColorPalette::Foreground]]; }
#backstageArea a.backstageSelTab {background:[[ColorPalette::Background]]; color:[[ColorPalette::Foreground]];}
#backstageButton a {background:none; color:[[ColorPalette::Background]]; border:none;}
#backstageButton a:hover {background:[[ColorPalette::Foreground]]; color:[[ColorPalette::Background]]; border:none;}
#backstagePanel {background:[[ColorPalette::Background]]; border-color: [[ColorPalette::Background]] [[ColorPalette::TertiaryDark]] [[ColorPalette::TertiaryDark]] [[ColorPalette::TertiaryDark]];}
.backstagePanelFooter .button {border:none; color:[[ColorPalette::Background]];}
.backstagePanelFooter .button:hover {color:[[ColorPalette::Foreground]];}
#backstageCloak {background:[[ColorPalette::Foreground]]; opacity:0.6; filter:'alpha(opacity=60)';}
/*}}}*/
/*{{{*/
* html .tiddler {height:1%;}

body {font-size:.75em; font-family:arial,helvetica; margin:0; padding:0;}

h1,h2,h3,h4,h5,h6 {font-weight:bold; text-decoration:none;}
h1,h2,h3 {padding-bottom:1px; margin-top:1.2em;margin-bottom:0.3em;}
h4,h5,h6 {margin-top:1em;}
h1 {font-size:1.35em;}
h2 {font-size:1.25em;}
h3 {font-size:1.1em;}
h4 {font-size:1em;}
h5 {font-size:.9em;}

hr {height:1px;}

a {text-decoration:none;}

dt {font-weight:bold;}

ol {list-style-type:decimal;}
ol ol {list-style-type:lower-alpha;}
ol ol ol {list-style-type:lower-roman;}
ol ol ol ol {list-style-type:decimal;}
ol ol ol ol ol {list-style-type:lower-alpha;}
ol ol ol ol ol ol {list-style-type:lower-roman;}
ol ol ol ol ol ol ol {list-style-type:decimal;}

.txtOptionInput {width:11em;}

#contentWrapper .chkOptionInput {border:0;}

.externalLink {text-decoration:underline;}

.indent {margin-left:3em;}
.outdent {margin-left:3em; text-indent:-3em;}
code.escaped {white-space:nowrap;}

.tiddlyLinkExisting {font-weight:bold;}
.tiddlyLinkNonExisting {font-style:italic;}

/* the 'a' is required for IE, otherwise it renders the whole tiddler in bold */
a.tiddlyLinkNonExisting.shadow {font-weight:bold;}

#mainMenu .tiddlyLinkExisting,
	#mainMenu .tiddlyLinkNonExisting,
	#sidebarTabs .tiddlyLinkNonExisting {font-weight:normal; font-style:normal;}
#sidebarTabs .tiddlyLinkExisting {font-weight:bold; font-style:normal;}

.header {position:relative;}
.header a:hover {background:transparent;}
.headerShadow {position:relative; padding:4.5em 0 1em 1em; left:-1px; top:-1px;}
.headerForeground {position:absolute; padding:4.5em 0 1em 1em; left:0px; top:0px;}

.siteTitle {font-size:3em;}
.siteSubtitle {font-size:1.2em;}

#mainMenu {position:absolute; left:0; width:10em; text-align:right; line-height:1.6em; padding:1.5em 0.5em 0.5em 0.5em; font-size:1.1em;}

#sidebar {position:absolute; right:3px; width:16em; font-size:.9em;}
#sidebarOptions {padding-top:0.3em;}
#sidebarOptions a {margin:0 0.2em; padding:0.2em 0.3em; display:block;}
#sidebarOptions input {margin:0.4em 0.5em;}
#sidebarOptions .sliderPanel {margin-left:1em; padding:0.5em; font-size:.85em;}
#sidebarOptions .sliderPanel a {font-weight:bold; display:inline; padding:0;}
#sidebarOptions .sliderPanel input {margin:0 0 0.3em 0;}
#sidebarTabs .tabContents {width:15em; overflow:hidden;}

.wizard {padding:0.1em 1em 0 2em;}
.wizard h1 {font-size:2em; font-weight:bold; background:none; padding:0; margin:0.4em 0 0.2em;}
.wizard h2 {font-size:1.2em; font-weight:bold; background:none; padding:0; margin:0.4em 0 0.2em;}
.wizardStep {padding:1em 1em 1em 1em;}
.wizard .button {margin:0.5em 0 0; font-size:1.2em;}
.wizardFooter {padding:0.8em 0.4em 0.8em 0;}
.wizardFooter .status {padding:0 0.4em; margin-left:1em;}
.wizard .button {padding:0.1em 0.2em;}

#messageArea {position:fixed; top:2em; right:0; margin:0.5em; padding:0.5em; z-index:2000; _position:absolute;}
.messageToolbar {display:block; text-align:right; padding:0.2em;}
#messageArea a {text-decoration:underline;}

.tiddlerPopupButton {padding:0.2em;}
.popupTiddler {position: absolute; z-index:300; padding:1em; margin:0;}

.popup {position:absolute; z-index:300; font-size:.9em; padding:0; list-style:none; margin:0;}
.popup .popupMessage {padding:0.4em;}
.popup hr {display:block; height:1px; width:auto; padding:0; margin:0.2em 0;}
.popup li.disabled {padding:0.4em;}
.popup li a {display:block; padding:0.4em; font-weight:normal; cursor:pointer;}
.listBreak {font-size:1px; line-height:1px;}
.listBreak div {margin:2px 0;}

.tabset {padding:1em 0 0 0.5em;}
.tab {margin:0 0 0 0.25em; padding:2px;}
.tabContents {padding:0.5em;}
.tabContents ul, .tabContents ol {margin:0; padding:0;}
.txtMainTab .tabContents li {list-style:none;}
.tabContents li.listLink { margin-left:.75em;}

#contentWrapper {display:block;}
#splashScreen {display:none;}

#displayArea {margin:1em 17em 0 14em;}

.toolbar {text-align:right; font-size:.9em;}

.tiddler {padding:1em 1em 0;}

.missing .viewer,.missing .title {font-style:italic;}

.title {font-size:1.6em; font-weight:bold;}

.missing .subtitle {display:none;}
.subtitle {font-size:1.1em;}

.tiddler .button {padding:0.2em 0.4em;}

.tagging {margin:0.5em 0.5em 0.5em 0; float:left; display:none;}
.isTag .tagging {display:block;}
.tagged {margin:0.5em; float:right;}
.tagging, .tagged {font-size:0.9em; padding:0.25em;}
.tagging ul, .tagged ul {list-style:none; margin:0.25em; padding:0;}
.tagClear {clear:both;}

.footer {font-size:.9em;}
.footer li {display:inline;}

.annotation {padding:0.5em; margin:0.5em;}

* html .viewer pre {width:99%; padding:0 0 1em 0;}
.viewer {line-height:1.4em; padding-top:0.5em;}
.viewer .button {margin:0 0.25em; padding:0 0.25em;}
.viewer blockquote {line-height:1.5em; padding-left:0.8em;margin-left:2.5em;}
.viewer ul, .viewer ol {margin-left:0.5em; padding-left:1.5em;}

.viewer table, table.twtable {border-collapse:collapse; margin:0.8em 1.0em;}
.viewer th, .viewer td, .viewer tr,.viewer caption,.twtable th, .twtable td, .twtable tr,.twtable caption {padding:3px;}
table.listView {font-size:0.85em; margin:0.8em 1.0em;}
table.listView th, table.listView td, table.listView tr {padding:0px 3px 0px 3px;}

.viewer pre {padding:0.5em; margin-left:0.5em; font-size:1.2em; line-height:1.4em; overflow:auto;}
.viewer code {font-size:1.2em; line-height:1.4em;}

.editor {font-size:1.1em;}
.editor input, .editor textarea {display:block; width:100%; font:inherit;}
.editorFooter {padding:0.25em 0; font-size:.9em;}
.editorFooter .button {padding-top:0px; padding-bottom:0px;}

.fieldsetFix {border:0; padding:0; margin:1px 0px;}

.sparkline {line-height:1em;}
.sparktick {outline:0;}

.zoomer {font-size:1.1em; position:absolute; overflow:hidden;}
.zoomer div {padding:1em;}

* html #backstage {width:99%;}
* html #backstageArea {width:99%;}
#backstageArea {display:none; position:relative; overflow: hidden; z-index:150; padding:0.3em 0.5em;}
#backstageToolbar {position:relative;}
#backstageArea a {font-weight:bold; margin-left:0.5em; padding:0.3em 0.5em;}
#backstageButton {display:none; position:absolute; z-index:175; top:0; right:0;}
#backstageButton a {padding:0.1em 0.4em; margin:0.1em;}
#backstage {position:relative; width:100%; z-index:50;}
#backstagePanel {display:none; z-index:100; position:absolute; width:90%; margin-left:3em; padding:1em;}
.backstagePanelFooter {padding-top:0.2em; float:right;}
.backstagePanelFooter a {padding:0.2em 0.4em;}
#backstageCloak {display:none; z-index:20; position:absolute; width:100%; height:100px;}

.whenBackstage {display:none;}
.backstageVisible .whenBackstage {display:block;}
/*}}}*/
/***
StyleSheet for use when a translation requires any css style changes.
This StyleSheet can be used directly by languages such as Chinese, Japanese and Korean which need larger font sizes.
***/
/*{{{*/
body {font-size:0.8em;}
#sidebarOptions {font-size:1.05em;}
#sidebarOptions a {font-style:normal;}
#sidebarOptions .sliderPanel {font-size:0.95em;}
.subtitle {font-size:0.8em;}
.viewer table.listView {font-size:0.95em;}
/*}}}*/
/*{{{*/
@media print {
#mainMenu, #sidebar, #messageArea, .toolbar, #backstageButton, #backstageArea {display: none !important;}
#displayArea {margin: 1em 1em 0em;}
noscript {display:none;} /* Fixes a feature in Firefox 1.5.0.2 where print preview displays the noscript content */
}
/*}}}*/
<!--{{{-->
<div class='header' macro='gradient vert [[ColorPalette::PrimaryLight]] [[ColorPalette::PrimaryMid]]'>
<div class='headerShadow'>
<span class='siteTitle' refresh='content' tiddler='SiteTitle'></span>&nbsp;
<span class='siteSubtitle' refresh='content' tiddler='SiteSubtitle'></span>
</div>
<div class='headerForeground'>
<span class='siteTitle' refresh='content' tiddler='SiteTitle'></span>&nbsp;
<span class='siteSubtitle' refresh='content' tiddler='SiteSubtitle'></span>
</div>
</div>
<div id='mainMenu' refresh='content' tiddler='MainMenu'></div>
<div id='sidebar'>
<div id='sidebarOptions' refresh='content' tiddler='SideBarOptions'></div>
<div id='sidebarTabs' refresh='content' force='true' tiddler='SideBarTabs'></div>
</div>
<div id='displayArea'>
<div id='messageArea'></div>
<div id='tiddlerDisplay'></div>
</div>
<!--}}}-->
<!--{{{-->
<div class='toolbar' macro='toolbar [[ToolbarCommands::ViewToolbar]]'></div>
<div class='title' macro='view title'></div>
<div class='subtitle'><span macro='view modifier link'></span>, <span macro='view modified date'></span> (<span macro='message views.wikified.createdPrompt'></span> <span macro='view created date'></span>)</div>
<div class='tagging' macro='tagging'></div>
<div class='tagged' macro='tags'></div>
<div class='viewer' macro='view text wikified'></div>
<div class='tagClear'></div>
<!--}}}-->
<!--{{{-->
<div class='toolbar' macro='toolbar [[ToolbarCommands::EditToolbar]]'></div>
<div class='title' macro='view title'></div>
<div class='editor' macro='edit title'></div>
<div macro='annotations'></div>
<div class='editor' macro='edit text'></div>
<div class='editor' macro='edit tags'></div><div class='editorFooter'><span macro='message views.editor.tagPrompt'></span><span macro='tagChooser excludeLists'></span></div>
<!--}}}-->
To get started with this blank [[TiddlyWiki]], you'll need to modify the following tiddlers:
* [[SiteTitle]] & [[SiteSubtitle]]: The title and subtitle of the site, as shown above (after saving, they will also appear in the browser title bar)
* [[MainMenu]]: The menu (usually on the left)
* [[DefaultTiddlers]]: Contains the names of the tiddlers that you want to appear when the TiddlyWiki is opened
You'll also need to enter your username for signing your edits: <<option txtUserName>>
These [[InterfaceOptions]] for customising [[TiddlyWiki]] are saved in your browser

Your username for signing your edits. Write it as a [[WikiWord]] (eg [[JoeBloggs]])

<<option txtUserName>>
<<option chkSaveBackups>> [[SaveBackups]]
<<option chkAutoSave>> [[AutoSave]]
<<option chkRegExpSearch>> [[RegExpSearch]]
<<option chkCaseSensitiveSearch>> [[CaseSensitiveSearch]]
<<option chkAnimate>> [[EnableAnimations]]

----
Also see [[AdvancedOptions]]
<<importTiddlers>>
!MyMatrizensumme
{{{
function r = summate(x,y);

[m,n] = size(x);
[o,p] = size(y);

if (m ~= o | n ~= p)
    error('Matrizen müssen die gleichen Zahlen an Spalten und Zeilen besitzen!');

else % Matrizenaddition
    r = zeros(m,n);

    for (zeile = 1:m) % Iteriere durch alle Zeilen
        for (spalte = 1:n) % Iteriere durch alle Spalten
            r(zeile, spalte) = x(zeile, spalte) + y(zeile, spalte);
        end;
    end;
end;

return;
}}}

!MySkalarmultiplikation
{{{
function r = scalarmultiply(x,y);

[m,n] = size(x);
[o,p] = size(y);

matrix = [];
scalar = 1;
rownumb = 0;
colnumb = 0;

if (m==1 & n==1) 
    scalar = x;
    matrix = y;
    rownumb = o;
    colnumb = p;
    
elseif (o==1 & p==1)
    scalar = y;
    matrix = x;
    rownumb = m;
    colnumb = n;

else
    error('Einer der Faktoren muss ein Skalar sein!');
    
end;


% Skalarmultiplikation
r = zeros(rownumb, colnumb);

for (zeile = 1:rownumb)
    for (spalte = 1:colnumb)
        r(zeile, spalte) = matrix(zeile, spalte) * scalar;
    end;
end;
    
return;
}}}

!MyMatrizenmultiplikation
{{{
function r = multiply(x,y);

[m,n] = size(x);
[o,p] = size(y);

if ((m == 1 & n == 1) | (o == 1 & p == 1))
    error('Argumente müssen Matrizen sein!');
elseif (n ~= o)
    error('Spaltenanzahl des ersten Faktors muss mit der Zeilenanzahl des zweiten Faktors übereinstimmen!');

else % Matrizenmultiplikation
    r = zeros(m,p);

    for (zeile1 = 1:m) % Iteriere durch alle Zeilen der linken Matrix
        for (spalte2 = 1:p) % Iteriere durch alle Spalten der rechten Matrix
            elem = 0;
            for (indx = 1:n) % Iteriere durch alle Spalten der linken Matrix (= Zeilen der rechten Matrix)
                wert1 = x(zeile1, indx);
                wert2 = y(indx, spalte2);
                elem += wert1 * wert2;
            end;
            r(zeile1, spalte2) = elem;
        end;
    end;
end;

return;
}}}
Das Lösen linearer Gleichungssysteme ist in Octave relativ einfach, dank spezieller eingebauter Funktionen. Trotzdem sind einige Dinge zu beachten, bevor man eine Gleichung durch den Prozessor jagt.

!Der einfachste Fall: Reguläre quadratische Koeffizientenmatrix
Eine reguläre quadratische Koeffizientenmatrix A~~nxn~~ besitzt ein Inverses A^^-1^^. Dadurch lässt sich Ax=b leicht umformen zu:
:x = A^^-1^^b
Um herauszufinden, ob eine quadratische Koeffizientenmatrix A~~nxn~~ regulär ist (also nicht singulär) berechnen wir dir Determinante von A. Falls die Determinante ungleich Null ist, ist die Gleichung invertierbar und damit lösbar.
Unsere entsprechende solve-Funktion lautet:
{{{
function r = solveRegular(A,b);
[m,n] = size(A);

if (m != n)
    fprintf('Koeffizientenmatrix ist nicht quadratisch!\n');
elseif (det(A) == 0)
    fprintf('Quadratische Koeffizientenmatrix ist nicht regulär!\n');
else
    r = inv(A) * b;
end;

return;
}}}
Die Berechnung einer Inversen ist jedoch relativ ineffizient und außerdem für singuläre Matrizen (also Matrizen ohne Inverse) nicht zu gebrauchen. Für reguläre Matrizen sollte man stattdessen auf das ''Gaußsche Eliminationsverfahren'' und für singuläre sowie nichtquadratische Koeffizientenmatrizen auf die ''Methode der kleinsten Quadrate'' zurückgreifen. Beide Methoden werden in Octave durch die Matrixdivision implementiert.

!Matrixdivision
Octave bietet eine bequeme Abkürzung für das Lösen linearer Gleichungssysteme: Den ''"""Slash-Operator"""''. Danach lässt sich Ax=b umformen zu:
: x = A \ b
Der Operator steht hierbei für verschiedene Lösungswege, je nachdem um welche Art Koeffizientenmatrix A es sich handelt.

!Reguläre quadratische Koeffizientenmatrix A (mit Matrixdivision)
:Der """Slash-Operator""" liefert die letzte Spalte der Ergebnismatrix aus dem ''Gaußschen Eliminationsverfahren'' ({{{rref()}}}) zurück. Es gilt:
{{{
R = rref([A b]);
[m n] = size(R);
A \ b == R(1:m,n)
}}}

!Singuläre quadratische Koeffizientenmatrix A
:Ist die Determinante von A Null ("nicht invertierbar"), gibt der """Slash-Operator""" eine Warnung zurück:
{{{
A = [1 1 1; 2 0 3; 3 1 4];
b = [2 5 6]';
A \ b;
warning: matrix singular to machine precision, rcond = 1.15648e-17
warning: attempting to find minimum norm solution
}}}
Dies bedeutet, dass Octave eine Näherungslösung durch die Methode der kleinsten Quadrate gefunden hat, obwohl das quadratische Gleichungssystem eine Determinante von Null und damit eigentlich keine Lösung besitzt. Dieses Problem tritt auch auf, wenn Octave eine Determinante erhält, die wegen physikalisch bedingter Ungenauigkeiten (siehe [[hier|Das Kreuz mit der Genauigkeit]]) nahe Null ist.

''Schlussfolgerung:'' Der """Slash-Operator""" ist bequem, aber gefährlich, da er in jedem Fall eine Lösung berechnet. Man muss also vor seiner Anwendung unbedingt überprüfungen, ob die Koeffizientenmatrix regulär ist oder nicht und gegebenenfalls eine Fehlermeldung ausgeben.
Mit diesen Vorsichtsmaßnahmen im Hinterkopf können wir unsere solve-Funktion durch den """Slash-Operator""" verbessern:
{{{
function r = solveRegular(A,b);
[m,n] = size(A);

if (m != n)
    fprintf('Koeffizientenmatrix ist nicht quadratisch!\n');
elseif (det(A) == 0)
    fprintf('Quadratische Koeffizientenmatrix ist nicht regulär!\n');
else
    r = A \ b;
end;

return;
}}}

!Singuläre überbestimmte Koeffizientenmatrix A
Es gibt noch eine andere Form der inverslosen singulären Matrizen, die ''nichtquadratischen Gleichungssysteme''. Solche Systeme haben entweder weniger Gleichungen als Unbekannte (unterbestimmt) oder mehr Gleichungen als Unbekannte (überbestimmt). Formal:
:A~~mxn~~x = b, m < n
und
:A~~mxn~~x = b, m > n
Beide Gleichungssysteme haben keine oder unendlich viele Lösungen, aber nur die überbestimmten können sich den Luxus leisten, einen ''bestmöglichen'' Wert anzugeben. Aus diesem Grund ist für diese unter dem """Slash-Operator""" eine Lösung definiert, die mit Hilfe einer """QR-Zerlegung""" im Sinne der Methode der kleinsten Quadrate die Lösung angibt, die das Quadrat des Fehlers zu jedem Punkt in der Matrix minimiert. Beispiel:
{{{
A = [2 -1; 1 1; 6 -1];
b = [2 5 -5]';
A \ b
}}}
Das Ergebnis ist definiert durch die ''Pseudoinverse'' der eigentlich nicht invertierbaren Koeffizientenmatrix. Die Pseudoinverse ist die Verallgemeinerung der inversen Matrix auf singuläre und nichtquadratische Matrizen:
:x = (A' * A)^^-1^^ * A' * b
Entsprechend in Octave:
{{{
inv(A' * A) * A' * b
}}}
Oder durch die eingebaute Funktion ''pinv'':
{{{
pinv(A) * b
}}}
Diese drei Methoden sind äquivalent zueinander.
Nun können wir die erlaubten Eingaben unserer solve-Funktion um singuläre Gleichungsysteme und einen entsprechenden Warnhinweis erweitern:
{{{
function r = solve(A,b);
[m,n] = size(A);

if (m < n)
    fprintf('Gleichungssystem ist unterbestimmt!\n');
elseif (m == n && det(A) == 0)
    fprintf('Quadratische Koeffizientenmatrix ist nicht regulär!\n');
else
    if (m > n)
      fprintf('Gleichungssystem überbestimmt, verwende Methode der kleinsten Quadrate...\n');
    end;
    r = A \ b;
end;

return;
}}}

//Quelle: Introduction to Octave, Dr. P.J.G. Long, University of Cambridge, Department of Engineering, 2005//
/%Background: #bbbbff
Foreground: #000
PrimaryPale: #99aacc
PrimaryLight: #006699
PrimaryMid: #002244
PrimaryDark: #000
SecondaryPale: #ffc
SecondaryLight: #fe8
SecondaryMid: #db4
SecondaryDark: #002244
TertiaryPale: #99aacc
TertiaryLight: #aaaaff
TertiaryMid: #000
TertiaryDark: #8B7355 
%/
Background: #eee
Foreground: #000
PrimaryPale: #8cf
PrimaryLight: #18f
PrimaryMid: #04b
PrimaryDark: #014
SecondaryPale: #ffc
SecondaryLight: #fe8
SecondaryMid: #db4
SecondaryDark: #841
TertiaryPale: #eee
TertiaryLight: #ccc
TertiaryMid: #999
TertiaryDark: #666
Error: #f88
Viele mathematischen Werkzeuge liefern abstrakte Lösungen zu einem Problem, Octave aber liefert ''konkrete numerische Lösungen''. Diese wichtige Eigenschaft kann in Octave zu einer Reihe von Merkwürdigkeiten führen.

Rechenergebnisse werden intern als """Double-Fließkommazahlen""" mit einer Genauigkeit von 64 Bit abgespeichert (also bis zu 15 Dezimalstellen). Je nach Anzahl der Zwischenergebnisse und Art der Berechnung leidet also die Genauigkeit mehr oder weniger stark.

Aus diesem Grund scheinen die Gesetze der Logik beim Verrechnen von Zahlen verschiedener Größenordnung Saltos zu springen. Ein Beispiel:
{{{
octave:#> x=1;
octave:#> while 1+x > 1
x = x/2;
end
octave:#> x
x = 1.1102e-016
}}}
Das Merkwürdige ist nicht das Ergebnis selbst, sondern dass überhaupt ein Ergebnis geworfen wird. Eigentlich müsste die Schleife ihr x bis in die Unendlichkeit halbieren. Warum terminiert sie also?
Die Erklärung ist, dass Octave hier mit Zahlen zwei verschiedener Größenordnungen rechnen muss (1 * 10^^0^^ und z.B. 1.234 * 10^^-16^^). Da Octave nicht in beiden beliebig genau arbeiten kann, ist die Summe aus 1 und einer sehr kleinen Fließkommazahl, deren erste von Null verschiedene Ziffer nach mehr als 15 Stellen kommt, schließlich wieder 1 und die Schleife bricht ab.

Konkret heißt dies:
: 1.000000000000001234
ist für Octave dasselbe wie:
: 1.0

Dazu kommt, dass Octave Zahlen (wie auch sonst) binär behandelt, was bei mehreren Rechenschritten zu frappierenden Ergebnissen führen kann. Ein Beispiel:
{{{
octave:#> 1 - 0.2 - 0.2 - 0.2 - 0.2 - 0.2
ans = 5.5511e-017
}}}
Warum ist das Ergebnis nicht Null, wie erwartet? Die Fließkommazahl 0.2 kann binär nicht mit einer endlichen Folge von Bits dargestellt werden (leicht nachzuprüfen [[hier|http://www.arndt-bruenner.de/mathe/scripts/Zahlensysteme.htm]]). Octave verwendet deshalb einen Näherungswert.

Für all diese Probleme gibt es keine konkrete Lösung. Für die Anwendungen in diesem Kurs reicht es, sich der Genauigkeitsschwankungen bewusst zu sein und Vorsicht walten zu lassen, wenn ihr zwei Zahlen vergleicht, verrechnet oder von einem exakten Ergebnis ausgeht.

Die Grundlegende Datenstruktur in Octave sind Matrizen. Variablen sind Matrizen mit nur einem Eintrag, Strings sind Vektoren aus Charakters, usw. Alle Variablen werden schwach dynamisch typisiert. Typumwandlungen können daher implizit erfolgen. Im folgenden eine kurze Erläuterung der Datenstrukturen in Octave:

!Numerische Objekte
Numerische Objekte sind Skalare, Vektoren und Matrizen, wobei alle drei intern als Matrizen von Skalaren gehandhabt werden (auch genannt "numerische Arrays"). Reelle und komplexe Zahlen werden standardmäßig als """Double-Fließkommazahlen""" initialisiert.
Nützliche Funktionen:
* ''realmin'': Zeigt die untere numerische Grenze
* ''realmax'': Zeigt die obere numerisch Grenze
* ''eps'': Zeigt die Genauigkeit des Systems
* ''isinteger(x)'': Ob Objekt eine """Integer-Zahl""" ist

Außerdem sind in Octave Typumwandlungen nach Integer verschiedener Bitgrößen und """Single-Fließkommazahlen""" möglich. Die Befehle lauten:
* ''single(x)''
* ''int8(x)''
* ''int16(x)''
* ''int32(x)''
* ''int64(x)''
Analog hierzu die "unsigned"-Varianten von int():
* ''uint8(x)''
* ''uint16(x)''
* ''uint32(x)''
* ''uint64(x)''

!Strings
Strings sind Zeilenvektoren von Charakteren, werden intern also als Matrizen realisiert. Alle entsprechenden Matrizenoperationen sind auf Strings anwendbar. Charaktermatrizen können mehrere Strings in einer Variablen speichern, wobei nicht besetzte Positionen kürzerer Strings mit einem vordefinierten Charakter besetzt werden, der standardmäßig ein leerer Charakter ist (siehe string_fill_char()).
{{{
octave:1> a = [ "s", "t", "r", "i", "n", "g"]
a = string
}}}
{{{
octave:2> string_fill_char("#")
octave:3> a = [ "s", "t", "r", "i", "n", "g"; "t", "e", "x", "t"]
a =

string
text##
}}}
{{{
octave:56> a = [ "noch"; "mehr"; "strings"]
a =

noch###
mehr###
strings
}}}
Nützliche Funktionen:
* ''ischar(A)'': Ob Objekt eine Matrix aus Charakteren ist
* ''isvector(A)'': Ob Objekt ein Vektor ist (in Verbindung mit ischar(): Ob Objekt ein gültiger String ist)
* ''val = string_fill_char()'': Zeigt Charakter an, der unbesetzte Positionen in Charaktermatrizen ausfüllt
* ''old_val = string_fill_char(new_val)'': Definiert Füllcharakter


!Strukturen
Variablen können unter einer Dachstruktur vereinigt werden. Der Name der Dachstruktur fungiert dann als Namensraum.
{{{
octave:1> x.a = 1; x.b = [1, 2; 3, 4]; x.c = "string";
octave:2> x.a
ans =  1
octave:3> x.b
ans =

   1   2
   3   4

octave:4> x.c
ans = string
octave:5> x
x =
{
  a =  1
  b =

     1   2
     3   4

  c = string
}
}}}

!Cell Arrays
Cell Arrays können im Gegensatz zu Matrizen ("numerischen Arrays") weitere nicht-skalare Datenstrukturen beinhalten. Die Zellen werden mit geschweiften Klammern initialisiert und abgefragt. ''Achtung!'' Der Index beginnt wie bei Matrizen bei 1!
{{{
octave:1> c = {"a string", rand(2, 2)};
octave:2> c{1}
ans = a string
}}}
Falls der Inhalt einer Zelle nicht als Element (also Matrix), sondern als weiteres Cell Array interpretiert werden soll, muss auf den Inhalt mit runden Klammern zugegriffen werden:
{{{
octave:1> c = {"1", "2", "3"; "a", "b", "c"; "4", "5", "6"};
octave:2> c{2,3}
ans = c
     
octave:3>c(2,3)
ans =
             {
               [1,1] = c
             }
}}}
Nützliche Funktionen:
* ''iscell(c)'': Ob ein Objekt ein Cell Array ist
* ''cell(x,y,z,...)'': Initialisiert ein multidimensionales Array mit leeren Matrizen als Zellen
Willkommen!
<!--{{{-->
<div class='toolbar' macro='toolbar [[ToolbarCommands::EditToolbar]]'></div>
<div class='title' macro='view title'></div>
<div class='editor' macro='edit title'></div>
<div macro='annotations'></div>
<div class='editor' macro='edit text'></div>
<div class='editor' macro='edit tags'></div><div class='editorFooter'><span macro='message views.editor.tagPrompt'></span><span macro='tagChooser excludeLists'></span></div>
<!--}}}-->
! Definition:
Ein """Nichtnull-Vektor""" v aus R^^n^^ ist ein Eigenvektor einer quadratischen Matrix aus R^^n×n^^, wenn das Produkt Av eine Verlängerung des Vektors v um den Faktor λ (Eigenwert) ist:
:Av = λv

! Berechnung:
:A ∈ R^^n×n^^
:Av = λv
:=> Av - λv = 0
:=> (A - λI)v = 0
Dies ist ein homogenes lineares Gleichungsystem. Eine nicht-triviale Lösung existiert wenn:
:rank(A - λI) < n
Also:
:det(A - λI) = 0
Dies entspricht einer Polynomfunktion n-ten Grades unter λ (siehe Berechnung von Determinanten). Ihre Nullstellen sind die Eigenwerte von A.
Die Eigenwerte setzen wir in die Gleichung (A - λI)v = 0 ein und erhalten mittels Gaußscher Elimination die Lösungsvektoren. Die Menge aller Eigenvektoren besteht aus allen von Null verschiedenen vielfachen der Lösungsvektoren. Falls zwei Vektoren Eigenvektoren zum gleichen Eigenwert λ sind, ist auch ihre Summe ein Eigenvektor.

! Funktionen in Octave:
:E = eig(A) berechnet alle Eigenwerte von A.
:[V,D] = eig(A) berechnet eine Diagonalmatrix D, die die Eigenwerte enthält und eine Matrix V mit den dazugehörigen Eigenvektoren. Es gilt also AV = VD. 

! Literatur
http://www.mia.uni-saarland.de/Teaching/MFI07/kap45.pdf
Bisher haben wir die Gaußsche Elimination ohne Pivotisierung implementiert. Dies kann zu einer Reihe von Problemen führen, zum Teil geschuldet der physikalischen Beschränkungen eines Rechners und den resultierenden Rundungsfehlern. Testen wir unser Modul {{{solveLE.m}}}.

Eine einfache Matrix mit kleinen Koeffizienten liefert das erwartete Ergebnis:
{{{
octave:1> A = [1 2 3; 2 5 8; 2 4 7]; b = [1 1 1];
octave:2> solveLE(A,b)
ans =

   2
   1
  -1
}}}

Auch mit Fließkommazahlen ist das Ergebnis korrekt, da die Anzahl der Dezimalstellen die von Octave unterstützte Genauigkeit nicht überschreitet:
{{{
octave:34> A = [3.2 3.6 7.6; 28 27 0; 0 0 15]; b = [66 165 90];
octave:35> solveLE(A,b)
ans =

   3.0000
   3.0000
   6.0000
}}}

Ein weiteres einfaches Beispiel scheitert allerdings aus naheliegenden Gründen:
{{{
octave:42> A = [0 2; 3 -2]; b = [4 5];
octave:43> solveLE(A,b)
warning: division by zero
warning: division by zero
ans =

   NaN
   NaN
}}}
Da eines der Pivotelemente Null ist, kann der Multiplikator während der Elimination nicht gebildet werden. Dieses Problem lässt sich durch eine ''partielle Pivotisierung'' lösen (oder "maximale Spaltenpivotsuche"). Hierbei wird aus den Koeffizienten unterhalb und einschließlich des Pivotelements der größte gewählt und die entsprechende Zeile mit der Pivotzeile vertauscht. Ist keines der Koeffizienten größer als Null, handelt es sich um ein ''überbestimmtes lineares Gleichungssystem'' und ist durch """LR-Zerlegung""" nicht lösbar (siehe stattdessen [[Methode der kleinsten Quadrate durch QR-Zerlegung]]) In diesem Beispiel nehmen wir die Zeilenvertauschung manuell vor und erhalten die richtige Lösung:
{{{
octave:44> A = [ 3 -2; 0 2]; b = [5 4];
octave:45> solveLE(A,b)
ans =

   3
   2
}}}

Auf die gleiche Weise lässt sich das Problem der Rundungsfehler lösen. Bei jedem Eliminationsschritt wird der Multiplikator durch Division der Koeffizienten einer Spalte durch das Pivotelement erzeugt. ''Der relative Fehler bei einer Division wird umso kleiner, je größer der Divisor ist.'' Das bedeutet, dass wir dafür Sorgen tragen sollten, dass stets der größte Koeffizient einer Spalte die Pivotrolle einnimmt. So lässt sich verhindern, dass sich die bei numerischen Berechnungen meist unvermeidlichen Fehler bei der Vorwärts/Rückwärtssubstitution unverhältnismäßig fortpflanzen und wachsen. Siehe dazu [[Gaußsche Elimination mit Pivotisierung]].
GNU Octave ist eine freie Software zur numerischen Lösung mathematischer Probleme, speziell solche der Matrizenrechnung. In Syntax und Umfang entspricht sie nahezu dem proprietären MATLAB.

!Installationspakete
* [[Linux|http://www.gnu.org/software/octave/download.html]] oder über Konsole: {{{sudo aptitude install octave}}}
* [[Windows und Mac OS|http://octave.sourceforge.net/]]
!Einführungen
* [[Variablen]]
* [[Datenstrukturen]]
* [[Kontrollstrukturen]]
* [[Module]]
* [[Skripte]]
* [[Zusammenfassung dieser Dokumentation als Präsentation|http://www.cip.ifi.lmu.de/~kaumanns/matrixmethoden/res/einfuehrung_in_octave.081110.odp]]
//Codestücke größtenteils aus der [[Octave-Dokumentation|http://www.gnu.org/software/octave/doc/interpreter/]].//
!"""Octave-Module""" Marke Eigenbau
* [[Allgemeine Beispiele]]
* [[Gaußsche Elimination ohne Pivotisierung]]
* [[Gaußsche Elimination durch LR-Zerlegung ohne Pivotisierung]]
* [[Gaußsche Elimination mit Pivotisierung (Module)]]
!Praxis
* [[Das Kreuz mit der Genauigkeit]]
* [[Wichtige Matrixfunktionen]]
* [[Automatisches Lösen linearer Gleichungssysteme]]
* Manuelle Lösung linearer quadratischer Gleichungssysteme
** [[Gaußsche Elimination handgemacht]]
** [[LR-Zerlegung handgemacht]]
** [[Erweiterung mit Pivotisierung]]
* [[Latent semantische Indizierung]]
!solveLE.m
{{{
function x = solveLE(A, b);

if (rows(b) == 1)
    b = b';
endif;

factors = lr_decomposition(A);
L = factors{1};
R = factors{2};

y = forSubst(L,b);

x = backSubst(R,y);

endfunction;
}}}

!lr_decomposition.m
{{{
function factors = lr_decomposition(A);

#A = pivotize(B);

[m n] = size(A);
if (m != n)
    fprintf('Error in lr_decomposition: Matrix is not square.\n');
    return;
endif;

L = eye(m,n);
R = A;

# Durchlaufe jede Zeile der Ausgangsmatrix
for (i = 1:m)
    # A(i,i) ist nun die Position des aktuellen Pivotelements
    # A(i,:) ist die aktuelle Pivotzeile
    # Der Multiplikator ist nun für jede kommende Zeile das Element unter dem Pivotelement geteilt durch das Pivotelement

    for (k = (i+1):m)
        multiplicator = R(k,i) / R(i,i);
        L(k,i) = multiplicator;

        for (j = i:n)
            # Durchlaufe nun alle Spalten, dh. jedes Element der aktuellen Zeile
            # Insgesamt wird Multiplikatorfache der Pivotzeile von der aktuellen Zeile subtrahiert
            R(k,j) -= R (i,j) * multiplicator;
        endfor;
    endfor;

endfor;

factors{1} = L;
factors{2} = R;

return;
}}}

!forSubst.m
{{{
function y = forSubst(A,b);

[m n] = size(A);
y = zeros(m,1);

if (m != n)
    fprintf('Error in forSubst: Coefficient matrix is not square.\n');
    return;
endif;

if (rows(b) != m)
    fprintf('Error in forSubst: Coefficient matrix and column vector do not have the same number of rows.\n');
    return;
endif;

for (i = 1:m)
    summ = 0;
    for (k = 1:(i-1))
        summ += A(i,k) * y(k,1);
    endfor;
    y(i,1) = (b(i) - summ) / A(i,i);
endfor;

return;
}}}

!backSubst.m
{{{
function x = backSubst(A,y);

[m n] = size(A);
x = zeros(m,1);

if (m != n)
    fprintf('Error in forSubst: Coefficient matrix is not square.\n');
    return;
endif;

if (rows(y) != m)
    fprintf('Error in forSubst: Coefficient matrix and column vector do not have the same number of rows.\n');
    return;
endif;

for (i = m:-1:1)
    summ = 0;
    for (k = (i+1):m)
        summ += A(i,k) * x(k,1);
    endfor;
    x(i,1) = (y(i) - summ) / A(i,i);
endfor;

return;
}}}
Fangen wir simpelst an: Ein lineares Gleichungssystem der Form
:Ax = b
lässt sich im Falle eine ''quadratischen regulären Koeffizientenmatrix A'' durch das Gaußsche Eliminationsverfahren lösen. Die """Octave-Module""" der folgenden Erläuterungen findet ihr unter [[Gaußsche Elimination ohne Pivotisierung]]. Die entsprechenden Algorithmen sind dort rekursiv implementiert und arbeiten mit der erweiterten Koeffizientenmatrix [A b] (anstatt getrennter A und b), was sich aus Gründen der Performance und Lesbarkeit eigentlich nicht anbietet. Um ein bisschen Octavecode zu zeigen, habe ich die """Beta-Beispiele""" aber so gelassen.

Das Muttermodul {{{gaussit_beta.m}}} sieht folgendermaßen aus:
{{{
function x = gaussit_beta(A, b);

if (rows(b) == 1)
    b = b';
endif;

# Gaussean Elimination
GaussMatrix = eliminate([A b]);

# Backwards Substitution
x = backSubst_recursive(GaussMatrix);

endfunction;
}}}
Falls der Ergebnisvektor b als Zeilenvektor eingegeben wurde, wird er transponiert. Die erweiterte Koeffizientenmatrix wird dann an die Eliminationsfunktion weitergegeben. Diese läuft nun rekursiv durch alle Zeilen und erstellt die obere Dreiecksform der Koeffizientenmatrix und gibt sie mit b erweitert zurück.

> Anmerkung: Die Funktion {{{eliminate}}} erschließt sich das aktuelle Rekursionslevel durch die Anzahl der Nullkoeffizienten vor dem Pivotelement. Das bedeutet, dass die Funktion Fehler schmeißt, wenn die Matrix ungünstigerweise ein Nullpivot enthält, was durch die fehlende Pivotisierung durchaus der Fall sein kann, ohne dass die Matrix dadurch unlösbar wird. Die Skripte in den folgenden Abschnitten sind besser gelöst.

Durch Rückwärtsersetzung wird die Dreiecksform schließlich gelöst und der Ergebnisvektor x zurückgegeben.
Weitaus praktischer und effizienter ist die Gaußsche Elimination in Form einer """LR-Zerlegung""", siehe Abschnitt [[LR-Zerlegung handgemacht]].
Alle Module sind unter [[Gaußsche Elimination mit Pivotisierung (Module)]] aufgeführt (inklusive ausführlicher Kommentare). Unser Muttermodul sieht wie folgt aus:
{{{
function x = solveLE_pivot(A);

n = length(A) - 1;

for (i = 1:n)
    perm(i) = i;
endfor

for (i = 1:(n-1))
    perm = pivotize(A, i, perm);
    
    if (perm == 0)
        printf("System nicht eindeutig lösbar.\n");
        return;
    endif;

    A = eliminate(A, i, perm);
endfor

if (A(perm(n),n) == 0)
    printf("System nicht eindeutig lösbar.\n");
    return;
endif

x = backwards_substitution(A, perm);

endfunction;
}}}
Der große Unterschied zur Gaußschen Elimination ohne Pivotisierung ist, dass bei jedem Schritt der Elimination die aktuelle Submatrix pivotisiert und die entsprechenden Zeilenvertauschungen in einem speziellen Permutationsvektor perm gespeichert werden.

Am Anfang zeigt jeder Eintrag an der Stelle i des Permutationsvektors auf die Zeile i der Koeffizientenmatrix. Bei jedem Pivotisierungsvorgang wird dieser Vektor aktualisiert. Jeder Zeilenzugriff während der gesamten Lösungsberechnung des Gleichungssystems darf nur (!) über diesen Permutationsvektor geschehen. Also z.B.: A(perm(i),n)
!solveLE_pivot.m
{{{
function x = solveLE_pivot(A);
% A: Erweiterte Koeffizientenmatrix (also eigentlich Ab)
% x: Ergebnisvektor

% length() gibt die Anzahl der Spalten der erweiterten Matrix zurück. Die Größe 
% Koeffizientenmatrix ist also um eins kleiner.
n = length(A) - 1;

% Wir erstellen keine Permutationsmatrix für die Pivotisierung. Stattdessen 
% speichern wir die Zeilenvertauschungen in einem "Permutationsvektor",
% einem Zeilenvektor, der an der j-ten Stelle die Zeilennummer i der 
% Koeffizientenmatrix enthält. Am Anfang, also in der umpermutierten Matrix, 
% entspricht j noch i.
for (i = 1:n)
    perm(i) = i;
endfor
% Ab jetzt dürfen wir auf die Matrix nur noch über den Eintrag in perm als 
% Zeilennummer zugreifen.

% Gaußsche Elimination: Für jede Submatrix der Koeffizientenmatrix...
for (i = 1:(n-1))
    % Pivotelemente sind der Reihe nach alle Elemente entlang der Diagonalen
    % Aktuelle Pivotzeile und Pivotspalte sind entsprechend die Teilvektoren, 
    % die zum aktuellen Pivotelement gehören.

    % Pivotisierung der Submatrix.
    % Aufruf:
    % neuer Permutationsvektor = pivotize(Matrix, Index der Submatrix, alter Permutationsvektor)
    perm = pivotize(A, i, perm);
    
    if (perm == 0)
        printf("System nicht eindeutig lösbar.\n");
        return;
    endif;

    % Elimination: Alle Elemente unterhalb des aktuellen Pivotelements werden
    % nun in Null verwandelt. Dazu wird zu jedem Zeilenvektor unterhalb der 
    % Pivotzeile ein vielfaches der Pivotzeile addiert. Der entsprechende 
    % Multiplikator errechnet sich aus dem Quotienten Element/Pivotelement.
    % Aufruf:
    % rechte obere Dreiecksmatrix Beta = eliminate(alte Matrix, Index der Submatrix, Permutationsvektor)
    A = eliminate(A, i, perm);
    
endfor

% Wenn ganz unten im b-Vektor eine Null steht, gibt es unendlich viele Lösungen.
if (A(perm(n),n) == 0)
    printf("System nicht eindeutig lösbar.\n");
    return;
endif

% Ansonsten: Rückwärtssubstitution
% Aufruf:
% Lösungsvektor = backwards_substitution(rechte obere Dreiecksmatrix, Permutationsvektor)
x = backwards_substitution(A, perm);

endfunction;
}}}

!pivotize.m
{{{
function perm = pivotize(A, i, perm);

    n = length(A) - 1;

    % Suche das größte Element im aktueller Spalte i unterhalb der Diagonalen:
    max = abs(A(perm(i),i)); % Aktuelles Max ist Pivotelement
    maxLine = perm(i); % Aktuelle Max-Zeile ist Pivotzeile
    
    for (j = (i+1):n) % Für jede Zeile unterhalb der Diagonalen...
        
        if abs(A(perm(j),i)) > max
            maxLine = j;
            max = abs(A(perm(j),i));
        endif
        
    endfor

    % Falls Max Null ist, ist das System unlösbar.
    if (max == 0)
        perm = 0;
        return;
    endif

    % Falls die Max-Zeile nicht gleich der Pivotzeile ist, müssen diese
    % vertauscht werden.
    if (perm(maxLine) != perm(i))
        tmp = perm(i);
        perm(i) = perm(maxLine);
        perm(maxLine) = tmp;
    endif

endfunction;
}}}

!eliminate.m
{{{
function A = eliminate(A, i, perm);

    n = length(A) - 1;

    for (j = (i+1):n) % Für jede Zeile unterhalb der Pivotzeile...
        
        multiplikator = A(perm(j),i) / A(perm(i),i); % Berechne Multiplikator
        
        for (k = (i+1):(n+1)) % Für jede Spalte rechts der Pivotspalte...
        
            A(perm(j),k) -= multiplikator * A(perm(i),k); % Berechne neuen Wert des Elements
        
        endfor
        
    endfor

endfunction;
}}}

!backwards_substitution.m
{{{
function x = backwards_substitution(A, perm);

n = length(A) - 1;

% Lösungsvektor x wird jetzt von hinten nach vorne mit Lösungselementen gefüllt.
x(n) = A(perm(n),n+1) / A(perm(n),n); % Anfang: Auflösung der ersten einfachen Gleichung

for (i = (n-1):-1:1) % Für jede Zeile von vorletzter bis erster...
    
    x(i) = A(perm(i),n+1); % Lösungselement ist Eintrag im b-Vektor
    
    for (j = (i+1):n) % Für jeden Koeffizienten der aktuellen Zeile außer dem ersten (erster Koeffient enthält die aufzulösende Variable)...
        x(i) -= A(perm(i),j) * x(j); % Neues Lösungselement ist Lösungselement minus ( Koeffizient mal bisheriger Eintrag im Lösungsvektor x)
    endfor
    
    x(i) /= A(perm(i),i); % Berechne fertiges Lösungselement (also aufzulösende Variable)
    
endfor
% Lösungsvektor x fertig. Wird zurückgegeben.

endfunction;
}}}
Die folgenden Module arbeiten mit Rekursion, im Gegensatz zu den fortgeschrittenen Modulen ab Abschnitt """LR-Zerlegung""".
!gaussit_beta.m
{{{
function x = gaussit_beta(A, b);

if (rows(b) == 1)
    b = b';
endif;

# Gaussean Elimination
GaussMatrix = eliminate([A b]);

# Backwards Substitution
x = backSubst(GaussMatrix);

endfunction;
}}}

!eliminate.m
{{{
function R = eliminate(A);

# Get valid pivot
curPivot = 0;
pivotIndex = 0;
while(curPivot == 0)
    pivotIndex++;
    curPivot = A(1,pivotIndex);
endwhile;

# Get pivot line
curPivotline = A(1,:);
[m n] = size(A);

# Final clause of recursion
if (m == 1)
    R = A;
    return;

# Eliminate all coefficients unter pivot element and recurse
else
    B = [];
    for (i = 2:m) # For each line under pivot line
        multiplicator = A(i,pivotIndex) / curPivot;
        B(i-1,:) = A(i,:) - multiplicator * curPivotline;
    endfor;

endif;

R = [curPivotline; eliminate(B)];
}}}

!backSubst.m
{{{
function R = backSubst(A);

[m n] = size(A);

if (m == 1)
    # Only one line left, therefore may we assume that we are on the lowest 
    # level on the equation where there is only one variable to determine
    R = A(1,n) / A(1,n-1);

else
    # Recurse on the matrix containing all lines except the first one
    # Get vector of solutions for all downward variables
    E = backSubst(A(2:m,:));

    # Determine which level of the system is currently active
    zeros = 0;
    for (i = 1:n)
        if (A(1,i) == 0)
            zeros++;
        else
            break;
        endif;
    endfor;

    # Solve equation and pass up vector of solutions
    s = 0;
    nE = rows(E);
    for (i = 1:(n-2-zeros))
        s = s + A(1,n-i) * E(nE-i+1, 1);
    endfor;

    R = [(A(1,n) - s) / A(1,n-zeros); E];

endif;

return;
}}}
! Dozent
* [[Prof. Dr. Klaus Schulz|http://www.cis.uni-muenchen.de/people/schulz.html]]
! Tutor
* David Kaumanns (david.kaumanns>!>@<!<gmail.com)
!"""If-Else-Struktur"""
Zu beachten ist der Gebrauch der """Short-Circuit-Operatoren""" && und ||, anstatt & und |. Letztere zwingen Octave, alle Argumente auszuwerten, bevor ein Wahrheitswert erzeugt wird, während """Short-Circuit-Operatoren""" von links nach rechts nur so viel auswerten, wie nötig ist.
''Wichtig!'' In """If-Klauseln""" können keine Stringvergleiche durchgeführt werden! {{{if (X == "string")}}} ist nicht gültig und sollte durch ein """Switch-Statement""" gelöst werden.
{{{
if (//condition//)
       //then-body//
     elseif (condition)
       //elseif-body//
     else
       //else-body//
endif
}}}

!"""While-Schleife"""
Der bekannte Gebrauch von {{{break}}} und {{{continue}}} ist in Octave ebenso möglich.
{{{
while (//condition//)
       //body//
endwhile
}}}

!"""Do-Until-Schleife"""
{{{
do
       //body//
until (//condition//)
}}}

!"""For-Schleife"""
{{{
for //var// = //expression//
       //body//
endfor
}}}

!"""Foreach-Schleife"""
//Expression// muss hier eine Struktur sein, siehe [[Strukturen|Datenstrukturen]].
{{{
for [ //val, key// ] = //expression//
       //body
endfor
}}}

!"""Switch-Struktur"""
//Label// kann ein Cell Array sein (//case { label1, label2}//), um zu fragen, ob //expression// einem der Labels entspricht.
{{{
switch expression
       case label
         command_list
       case label
         command_list
       ...
       otherwise
         command_list
     endswitch
}}}

!"""Continuation Lines"""
Befehle werden in Octave durch Semikolon oder Newline abgeschlossen. Soll ein Befehl auf mehrere Zeilen aufgeteilt werden, verwendet man {{{/}}}. Innerhalb von runden Klammern (zB. in der Klausel einer """If-Struktur""") ist dies nicht notwendig.
{{{
x = 1 + 2 \
    + 3 \
    + 4;
}}}
Im folgenden wird die manuelle """Octave-Implementation""" der Gaußschen Elimination als ''"""LR-Zerlegung"""'' (bzw. ''"""LU-Zerlegung"""'' oder ''Dreieckszerlegung'') präsentiert. Die entsprechenden """Octave-Module""" findet man unter [[Gaußsche Elimination durch LR-Zerlegung ohne Pivotisierung]].

Die """LR-Zerlegung""" scheint auf den ersten Blick mehr Aufwand zu produzieren als die einfache Gaußsche Elimination. Für die praktische Anwendung ist sie allerdings sinnvoller, da auch für viele verschiedene rechte Seiten b die rechenaufwändige Elimination von A nur ein einziges Mal durchgeführt werden muss. Möchte man das Gleichungssystem mit einer anderen rechten Seite b lösen, muss lediglich die Vorwärts- und Rückwärtsersetzung wiederholt werden.

Das Muttermodul unserer Implementation heißt {{{solveLE.m}}} und wird zwei Argumenten aufgerufen, der Koeffizientenmatrix A und der rechten Seite b:
{{{
function x = solveLE(A, b);

if (rows(b) == 1)
    b = b';
endif;

factors = lr_decomposition(A);
L = factors{1};
R = factors{2};

y = forSubst(L,b);

x = backSubst(R,y);

endfunction;
}}}
Gesucht ist ein Spaltenvektor x, für den gilt:
:Ax = b
Hierzu wird A zuerst durch die Funktion {{{lr_decomposition}}} in eine linke untere Dreiecksmatrix L und eine rechte obere Dreiecksmatrix R mit besonderen Eigenschaften zerlegt. Es soll gelten:
:A = L * R
* R ist die bekannte Gaußsche Transformationsmatrix mit der oberen rechten Dreiecksform.
* L ist eine erweiterte Identitätsmatrix (dh. Diagonalmatrix mit Einsen auf der Diagonale). Für eine normale Identitätsmatrix I gilt A = A * I. Die Matrix L enthält jedoch zusätzlich im linken unteren Dreieck die Multiplikatoren aus der Gaußschen Elimination. Zur Erinnerung: Wenn in einer Spalte ein Koeffizient unter dem Pivotelement eliminiert werden soll, muss man von der entsprechenden Zeile das Produkt aus der Pivotzeile und einem speziellen Faktor subtrahieren. Dieser Faktor ist das Verhältnis Koeffizient zu Pivotelement. Pro zu eliminierendem Element ergibt sich also ein Faktor, welcher in die Eliminationsmatrix L geschrieben wird, und zwar in die gleiche Position wie das zu eliminierende Element. Die Dreiecksform von L ergibt sich so automatisch.
Nun können wir unser Ausgangsproblem umschreiben:
:Ax = L * R * x = b
In der klassischen Gaußschen Elimination würden wir einfach eine Rückwärtssubstitution der Transformationsmatrix durchführen, welche in diesem Fall R ist. Leider steht uns da die Eliminationsmatrix L im Weg. Deshalb lösen wir zuerst die Gleichung
:Ly = b
für y = Rx. Dies geschieht durch Vorwärtssubstitution von L unter b mit dem entsprechenden Funktionsaufruf von {{{forSubst}}}. Anschließend lösen wir die Gleichung
:Rx = y
durch Rückwärtssubstitution von R unter y mit Aufruf von {{{backSubst}}}. Das Ergebnis ist der Lösungsvektor x.

In der Praxis sollte während der Elimination eine Pivotisierung (mit Ausgabe entsprechender Permutationsmatrix) geschehen, siehe dazu [[Erweiterung mit Pivotisierung]].
Das folgende Kapitel erklärt die praktische Umsetzung von LSI mit Octave und Perl. Sämtliche Skripte und Dateien können [[hier|http://www.cip.ifi.lmu.de/~kaumanns/matrixmethoden/res/lsi_octave.tar.gz]] heruntergeladen werden.
Das """lsi-Skript""" kann anhand der beiden Beispielsets sofort ausprobiert werden:
*lsi("tf_set1_matrix.csv", "tf_q1_matrix.csv");
*lsi("tf_set2_matrix.csv", "tf_q2_matrix.csv");
Spezielle Beispiele für das Beispielset Nummer 1 (aus Sebastians Referat) müssen entsprechend einkommentiert werden. Achtung: Die folgenden Erläuterungen beziehen sich auf das Beispielset Nummer 2.

!Umriss
Die Berechnung der Ähnlichkeit einer Anfrage mit jeweils jedem Dokument eines Korpus besteht aus den folgenden Schritten:
* Preprocessing
** Generierung der """Term-Dokument-Matrix""" X aus den Dokumenten (z.B. mit Termfrequenzen oder """Tf-idf-Maß""")
** Generierung des """Query-Vektors""" q aus der Anfrage (z.B. mit Termfrequenzen oder """Tf-idf-Maß""")
* LSI
** Singulärwertzerlegung und """k-Approximierung""" der """Term-Dokument-Matrix"""
** Erstellung des Pseudodokumentes aus q auf der Basis der """k-Approximierung""" (also Abbildung von q im semantischen Raum)
** Berechnung der """Cosinus-Abstände""" zwischen dem Pseudodokumentvektor und den Dokumentvektoren
** Absteigende Sortierung nach Abstand

Für die Erstellung des Pseudodokumentes benötigen wir einen auf die Termdimension von X abgestimmen Spaltenvektor q. Das Preprocessing erledigen lagern wir der Einfachheit halber in zwei """Perl-Skripte""" aus. Die folgenden Erläuterungen beziehen sich auf drei kurze Beispieldokumente d1, d2, d3 (im Ordner res2) sowie einer Anfrage q (als Datei q2.txt):
*d1: "Shipment of gold damaged in a fire."
*d2: "Delivery of silver arrived in a truck."
*d3: "Shipment of gold arrived in a truck."
*q: "gold silver truck"

!Preprocessing
!!build_td_matrix.perl
Für unser erstes einfaches Beispiel auf die drei kurzen Dokumente d1, d2 und d3 ignorieren wir die Stopwortliste und erstellen eine """Term-Dokument-Matrix""" X mit einfachen Termfrequenzen.
<<<
{{{perl build_td_matrix.perl -t -r res2 -n set2}}}
<<<
!!build_query_matrix.perl
Außerdem benötigen wir einen auf X abgeglichenen Termvektor q. Abgleichen bedeutet hier, dass q alle Terme aus X enthält. Falls ein Term der Anfrage nicht in X vorkommt (also kein Term des Dokumentensets ist), wird er auch nicht in q aufgeführt.
<<<
{{{perl build_query_matrix.perl -t -m tf_set2_matrix.csv -q q2.txt -n q2}}}
<<<
!!Ergebnis
Beide Skripte erzeugen Matrizen der Mindestgröße 2x2. Die erste Zeile enthält die Dokumentnamen, die erste Spalte die alphabetisch sortierten Terme.
<html><img src="./img/lsi1_td-matrix.png" style="width: 400px; "/></html>
Die entsprechenden Dateien sehen aus wie folgt:
!!!tf_set2_matrix.csv
{{{
,d1.txt,d2.txt,d3.txt
a,1,1,1
arrived,0,1,1
damaged,1,0,0
delivery,0,1,0
fire,1,0,0
gold,1,0,1
in,1,1,1
of,1,1,1
shipment,1,0,1
silver,0,2,0
truck,0,1,1
}}}
!!!tf_query_matrix.csv
{{{
,q2.txt
a,0
arrived,0
damaged,0
delivery,0
fire,0
gold,1
in,0
of,0
shipment,0
silver,1
truck,1
}}}


!LSI
!!Singulärwertzerlegung
Aus den beiden """CSV-Dateien""" extrahieren wir mit Octave zwei Matrizen X und q.
<<<
{{{
X = dlmread("tf_set2_matrix.csv", ',', 1, 1);
q = dlmread("tf_q2_matrix.csv", ',', 1, 1);
}}}
<<<
Mittels der """svd-Funktion""" führen wir eine Singulärwertzerlegung durch. Man beachte, dass Octave die """D-Matrix""" automatisch transponiert.
<<<
{{{
[T S D] = svd(X);
}}}
<<<
Das Ergebnis der Funktion sind zwei orthogonale Matrizen T und D sowie eine Diagonalmatrix mit den Singulärwerten. In diesem Stadium entspricht jedes Dokument einer abstrakten Semantischen Richtung im Dokumentenset.
<html><img src="./img/lsi2_svd.png" style="width: 450px; "/></html>
!!"""k-Approximierung"""
Durch die Singulärwertzerlegung sind die Spalten von T, die Zeilen von D und die Diagonalelemente von S absteigend nach Wichtigkeit der durch sie dargestellten semantischen Richtung sortiert. Wir können also die unwichtigsten semantischen Richtungen (semantisches Rauschen) bequem abschneiden, beziehungsweise uns auf die k wichtigsten semantischen Richtungen beschränken. Dieser Schritt wird """k-Approximierung""" genannt.
<<<
{{{
k = 2;
S_k = S(1:k, 1:k);
T_k = T(:, 1:k);
D_k = D(:, 1:k);
}}}
<<<
Das Ergebnis ist ein in diesem Falle auf zwei semantische Richtungen beschränkter semantischer Raum, in dem alle Dokumente als Vektoren abgebildet werden können. Der Vektor eines Dokumentes ist der entsprechende Zeilenvektor aus D_k.
<html><img src="./img/lsi3_svd-approx.png" style="width: 550px; "/></html>
!!Erstellung des Pseudodokumentes
Nach der """k-Approximierung""" der """TD-Matrix""" ist es nicht mehr möglich, den Anfragevektor q im gleichen Raum wie die Dokumente zu platzieren. Wir müssen also aus q einen Vektor ableiten, der sich im approximierten semantischen Raum darstellen lässt. Dieser Vektor ist das sogenannte Pseudodokument. Die Ableitung geschieht über:
<<<
{{{
pseudodoc = q' * T_k * S_k^(-1);
}}}
<<<
Für unser Beispiel lässt sich die Berechnung wie folgt veranschaulichen:
<html><img src="./img/lsi4_pseudodokument.png" style="width: 550px; "/></html>
!!Vektorenvergleich
Die vier Vektoren werden wie folgt in unserem 2-approximierten semantischen Raum platziert:
<html><img src="./img/lsi5_semantischer_raum.png" style="width: 550px; "/></html>
Wir sehen bereits, dass d2 das Gewinnerdokument ist, gefolgt von d3 und schließlich d1. Die Berechnung erfolgt über den Cosinusabstand zwischen dem Pseudodokumentvektor und den einzelnen Dokumentvektoren, also den Zeilenvektoren aus D_k.
<<<
{{{
printf("Query-Doc-Similarities:\n");

for (i = 1:rows(DS))
    results(i,1) = cosine(pseudodoc, DS(i, :));
endfor

[s, indx] = sort(results);

for (i = 1:rows(indx))
    nb = rows(indx) - i + 1;
    printf("\tDocument %s: %s\n", int2str(indx(nb,1)), num2str(results(indx(nb,1),1)));
endfor
}}}
<<<
Das Ergebnis bestätigt unsere Schätzung:
<<<
Document 2: 0.99099
Document 3: 0.44796
Document 1: -0.053951
<<<
!!Verrechnung der Singulärwerte in S_k
Anstatt das Pseudodokument nur mit den Zeilenvektoren aus D_k zu vergleichen, kann man es auch mit den Zeilenvektoren aus dem Matrizenprodukt D_k*S_k vergleichen. Während D_k ein Dokument nur im Hinblick auf seinen Bindungen zu den semantischen Richtungen im Raum abbildet, berücksichtigt D_k*S_k auch die Wichtigkeit einer semantischen Richtung im Dokumentenset (durch die Singulärwerte). Dadurch werden i.d.R. zwar die absoluten Ähnlichkeiten beeinflusst, nicht aber die Reihenfolge der Dokumente.

!Allgemeine Vergleiche
Mit Hilfe der angehängten Funktionsdateien können einzelne Vergleichen zwischen Termen und Dokumenten des Dokumentensets vorgenommen werden:
* sim_term_term(T_k, S_k, term1, term2, td-matrix-file.csv)
* sim_doc_doc(D_k, S_k, doc1, doc2, td-matrix-file.csv)
* sim_term_doc(T_k, S_k, D_k, term, doc, td-matrix-file.csv)
Bei den Vergleichen """Term-Term""" bzw. """Doc-Doc""" können entweder die Matrizenprodukte T_k*S_k bzw. D_k*S_k verwendet werden, um die Koordinaten der Vektoren zu extrahieren, oder aber die nur gesamte approximierte """Term-Dokument-Matrix""" X_approx. Das Ergebnis ist das gleiche, bringt aber erhebliche Geschwindigkeitsunterschiede mit sich.

Beispiel """Dokument-Dokument-Vergleich""": Da X_approx die Relationen zwischen Termen und Dokumenten angibt und der Termvektor eines Dokumentes entsprechend groß werden kann, dauert der Cosinusvergleich zwischen zwei Spaltenvektoren von X_approx ungleich länger als zwischen zwei Zeilenvektoren von D_k*S_k. Zur Veranschaulichung: In unserem Dokumentenset 1 haben wir 1789 verschiedene Terme, 16 verschieden Dokumente und (nach der Approximation) 2 semantische Richtungen. Es gelten die Größen:
<<<
{{{
[rows columns] = size(X_k)
    rows =  1789
    columns =  16
[rows columns] = size(D_k*S_k)
    rows =  16
    columns =  2
}}}
<<<
Wir haben somit zwei verschiedene Möglichkeiten, ein und dasselbe Dokument zu repräsentieren.
#Als Vektor im semantischen Raum (durch D_k*S_k)
#Als Vektor in der """Term-Dokument-Matrix""" (durch X_k)
Mit anderen Worten: X_k löst die Relationen zwischen Termen und Dokumente auf, während D_k*S_k diese Beziehung auf den semantischen Raum projeziert (und damit abstrahiert). Die Vorteile sind offensichtlich Effizienz und Wiederverwendbarkeit, da D_k*S_k nur einmal berechnet werden muss.

Bei """Term-Term-Vergleichen""" gelten die  gleichen Prinzipien: Einen Term können wir durch einen Vektor im semantischen Raum (durch T_k*S_k) oder in X_k repräsentieren. Eine große Anzahl an Dokumenten würde sich bei der Verwendung von X_k rächen, während T_k*S_k pro Term nur zwei Dimensionen liefert:
<<<
{{{
[rows columns] = size(T_k*S_k)
    rows =  1789
    columns =  2
}}}
<<<

!Anhang
Codestücke zur Initialisierung der Vektoren und Matrizen für das Testen der """Similarity-Funktionen""":
{{{
X = dlmread("tf_set1_matrix.csv", ',', 1, 1);
q = dlmread("tf_q1_matrix.csv", ',', 1, 1);
[T S D] = svd(X);
k = 2;
S_k = S(1:k, 1:k);
T_k = T(:, 1:k);
D_k = D(:, 1:k);
pseudodoc = q' * T_k * S_k^(-1);
}}}
{{{
X = dlmread("tf_set2_matrix.csv", ',', 1, 1);
q = dlmread("tf_q2_matrix.csv", ',', 1, 1);
[T S D] = svd(X);
k = 2;
S_k = S(1:k, 1:k);
T_k = T(:, 1:k);
D_k = D(:, 1:k);
pseudodoc = q' * T_k * S_k^(-1);
}}}

!Bildernachweis:
Latent Semantic Indexing, A Fast Track Tutorial, Dr. Edel Garcia, 2006
; Adjungierte Matrix A*:
> Entspricht bei Matrizen über R der transponierten Matrix AT

; Determinante
> Funktion, die einer quadratischen Matrix einen Skalar zuordnet. Schreibweise: det(A) oder |A|. Wenn die Determinante ungleich Null ist, ist die Matrix invertierbar und das zugehörige lineare Gleichungssystem eindeutig lösbar.

; Dyadisches Produkt (outer product)
> Matrizenprodukt aus Vektoren x und y: xy^^T^^. Erzeugt Matrix.

; [[Eigenwerte/ Eigenvektoren]]

; Eigenwerte:
> Jeweilige Faktoren λ der Eigenvektoren einer quadratischen Matrix.

; Einheitsvektor
> Normierter Vektor der Länge (=Norm) eins. Kann aus einem Vektor erzeugt werden, indem man ihn durch seine Länge teilt.

; Gaußsche Elimination
> Erzeugung der oberen Dreiecksmatrix eines linearen Gleichungssystems durch Vorwärtselimination. Kann mit oder ohne Pivotisierung erfolgen.

; Homogenes lineares Gleichungssystem
> Lineares Gleichungssystem mit rechter Seite gleich 0 (b ist Nullvektor).

; Multiplikator
> Quotient des Koeffizienten der zu eliminierenden Variablen durch das Pivotelement.

; Normalenvektor einer Ebene
> Auf Länge 1 normierter Vektor, der senkrecht (orthogonal) auf einer Ebene steht. Eine Ebene wird durch ihren Normalenvektor eindeutig definiert.

; Orthogonalbasis
> Menge von zueinander orthogonalen Vektoren, die einen Vektorraum aufspannen.

; Orthonormalbasis
> Orthogonalbasis mit auf die Länge eins normierten Vektoren.

; """Pivot-Element"""
> Koeffizient der zu multiplizierenden, später unverändert bleibenden Gleichung zu der Variablen, die in der nächsttieferen Gleichung eliminiert werden soll.

; [[QR-Zerlegung durch Householdertransformation]]

; Skalarprodukt (inner product)
> Allgemein: Verknüpfung zwischen zwei Vektoren x und y, die einen Skalar erzeugt. Verschiedene Berechnungen sind möglich:
> - Matrizenprodukt: x^^T^^y.
> - Geometrische Betrachtung: |x|×|y|×cos(x,y)
> Wichtige Eigenschaften:
> - Das Skalarprodukt entspricht der quadrierten 2-Norm (Euklidische Norm).
> - Das Skalarprodukt zweier """Nichtnull-Vektoren""" ist genau dann Null, wenn ihr Winkel 90° beträgt, sie also orthogonal sind.

; Unitäre Matrix:
> Entspricht bei Matrizen über R der orthogonalen Matrix. Es gilt: A*×A=I

; Vorwärtselimination
> Schrittweise Entfernung der Koeffizienten der Zeilen eines linearen Gleichungssystems von rechts nach links und oben nach unten. Entfernung geschieht durch Verwandlung des zu eliminierenden Koeffizienten in Null, indem zu der zu eliminierenden Zeile eine Skalarmultiplikation (siehe Multiplikator) der vorherigen Zeile addiert wird.
Hier findet ihr die eingesendeten Referate sowie Einführungen zu einigen Themen aus der linearen Algebra, die für uns besonders wichtig sind. Die Einführungen sollen den Stoff aus einer anderen Perspektive beleuchten und besonders auf die Aspekte eingehen, die für uns wichtig sind bzw. die ich für große Verständnisstolperfallen halte.
Bei Fragen, Korrekturen, Ergänzungen oder Themenwünschen: Schreibt mir!

[[Lexikon wichtiger Begriffe]]
* [[Lösbarkeit von linearen Gleichungssystemen]]
* [[Referat: Vektoren und Matrizen (pdf)|http://www.cip.ifi.lmu.de/~kaumanns/matrixmethoden/res/ref_vektoren_und_matrizen.pdf]]
* [[Referat: Methode der kleinsten Quadrate (pdf)|http://www.cip.ifi.lmu.de/~kaumanns/matrixmethoden/res/ref_methode_der_kleinsten_quadrate.pdf]]
* [[QR-Zerlegung durch Householdertransformation]]
* [[Eigenwerte/ Eigenvektoren]]
* [[Referat: Singulärwertzerlegung (pdf)|http://www.cip.ifi.lmu.de/~kaumanns/matrixmethoden/res/ref_svd.pdf]]
* [[Referat: Latent semantisches Indexieren (pdf)|http://www.cip.ifi.lmu.de/~kaumanns/matrixmethoden/res/ref_latent_semantisches_indexieren.pdf]]
* [[Referat: Key Word and Key Sentence Extraction (pdf)|http://www.cip.ifi.lmu.de/~kaumanns/matrixmethoden/res/ref_key_word_extraction.pdf]]
* [[Referat: PageRank (pdf)|http://www.cip.ifi.lmu.de/~kaumanns/matrixmethoden/res/ref_pagerank.pdf]]
* [[Referat: HITS (odt)|http://www.cip.ifi.lmu.de/~kaumanns/matrixmethoden/res/ref_hits.odt]]
Gegeben ist ein lineares Gleichungssystem der Form:
@@A * x = b@@

!Scheitern des Gaußschen Eliminationsverfahrens
!! Echtes Versagen ohne Lösung
> x - 2y = 1<br>3x - 6y = 11
Ergebnis der Elimination:
> 0y = 8
!! Echtes Versagen mit unendlich vielen Lösungen
> x - 2y = 1<br>3x - 6y = 11
Ergebnis der Elimination:
> x - 2y<br>0y = 0
!!Vorübergehendes Versagen
>0x + 2y = 4<br>3x - 2y = 5
Der Multiplikator wäre zu berechnen durch:
: 3/0
Lösung des Problems: ''Pivotisierung''. Vertauschung von Zeilen und/oder Spalten der Gesamtmatrix zu einem eliminierbaren linearen Gleichungssystem.


!Zwei Grundfragen
* Gibt es eine Lösung?
* Wenn ja, ist die Lösung eindeutig?

!Die Bedeutung der linearen Unabhängigkeit

Der Vektor @@b@@ ist also eine ''Linearkombination'' der Spaltenvektoren von @@A@@. Das bedeutet, dass die Summe der Spaltenvektoren von @@A@@ multipliziert mit bestimmten Faktoren den Vektor @@b@@ als mögliches Ergebnis haben muss, damit die Gleichung lösbar ist.

Damit dies der Fall ist, müssen alle Spaltenvektoren von @@A@@ linear unabhängig sein, dh. @@A@@ muss ''vollen Rang r'' besitzen. Das bedeutet, dass Summe der Spaltenvektoren niemals im Nullvektor enden darf, außer alle Faktoren sind Null (triviale Lösung). Da der Vektor @@b@@ die ''Linearkombination'' der r unabhängigen Spaltenvektoren ist, sind @@b@@ und die Spaltenvektoren ''linear abhängig''. Das bedeutet, dass die ''erweiterte Matrix @@(A b)@@'' ebenfalls den Rang r haben muss, damit die Gleichung lösbar ist.

!Folgerungen
;Ist eine Koeffizientenmatrix @@A@@ invertierbar, so ist die Gleichung immer und eindeutig lösbar: @@x = A^^-1^^ * b@@
:Begründung: Eine reguläre (=invertierbare) Matrix @@Anxn@@ hat vollen Rang r, dh. jede erweiterte Matrix @@(A b)@@ hat den ''gleichen Rang r''.

;Ist @@b@@ der Nullvektor, so ist heißt das Gleichungssystem @@Ax = 0@@ ''homogen'' und ist immer lösbar.
:Begründung: Die durch den Nullvektor erweiterte Matrix ändert nicht ihren Rang, da der Nullvektor zu allen Spaltenvektoren ''linear abhängig'' ist. Die Lösung ist also immer mindestens der Nullvektor: @@A0 = 0@@
[[Start|Willkommen!]]
[[Termine]]
----
[[Material]]
[[GNU Octave]]
[[Lineare Algebra]]
----
[[Kontakt]]
!"""Octave-Module""" und -Skripte
Meine (Davids) aktuellen Programmbeispiele könnt ihr [[hier|http://www.cip.ifi.lmu.de/~kaumanns/matrixmethoden/octave.tar.gz]] """als tar.gz-Paket""" herunterladen. Der Pakken wird permanent erneuert/verbessert/debugt/erweitert, ein neuer Klick auf der Link lohnt sich also öfter als seltener.
!LSI: """Perl-Skripte"""
* [[build-td-matrix.perl]]
* [[build-query-matrix.perl]]
!Verweise
* [[Kursseite WS 2008/2009|http://www.pms.ifi.lmu.de/lehre/seminar/information-retrieval/08ws09/]]
* Kurze Einführung in Octave
:http://www.tu-harburg.de/rzt/tuinfo/software/numsoft/Einf_Octave.html
* Kurze Tutorials
:http://ww.christianherta.de/octaveMatlabTutorial.html
:http://en.wikibooks.org/wiki/Octave_Programming_Tutorial
* Erweiterte Tutorials
:http://www3.informatik.uni-wuerzburg.de/staff/menth/Lehre/matlab-octave-tutorial.pdf
:http://www.amm.mw.tum.de/fileadmin/Image_Archive/Lehre/Prakt_MKS/Tutorial.pdf
* """QtOctave""": grafische """Open-Source-Oberfläche""" für Octave
:http://qtoctave.wordpress.com/download/
Module (bzw. Funktionen) sind ausgelagerte Programmteile, die von der Eingabeaufforderung oder von einem Skript aus aufgerufen werden können. Im folgenden werden kurz die Besonderheiten der """Octave-Funktionen""" erläutert

!Syntax
Jede Moduldatei beginnt mit dem Schlüsselwort {{{function}}}, der Ergebnisvariablen, dem Funktionsnamen, der gleichzeitig der Dateiname ist, und den Funktionsparametern:
{{{
function result = do_something(x, y);
...
return;
}}}
Die Angabe von {{{return}}} ist nicht nötig, kann aber verwendet werden, um innerhalb einer Kontrollstruktur die Funktion vorzeitig zu verlassen. Anstelle von {{{return}}} kann man auch den Befehl {{{endfunction}}} verwenden.
''Wichtig!'' Funktionsargumente werden ''immer'' als Kopie übergeben! Referenzen existieren in Octave nicht!

!Ergebnisvektoren
Eine praktische Eigenschaft von Funktion in Octave ist, dass sie mehr als ein Ergebnis zurückgeben können. Die Ergebnisse werden dabei in einem Zeilenvektor gespeichert:
{{{
function [a b c] = do_something(x, y, z);
    a = x;
    b = y;
    c = z;
return;
}}}

!Rekursion
Selbstaufrufe sind ebenfalls möglich und funktionieren nach den bekannten Regeln. Über die """built-in-Variablen"""
* ''val = max_recursion_depth ()''
* ''old_val = max_recursion_depth (new_val)''
kontrolliert Octave die maximal mögliche Anzahl von Rekursionsschritten.

!Dynamische Verwaltung der Argumentliste
Die Anzahl der Funktionsargumente muss nicht unbedingt bekannt sein. Potentiell unendlich viele Argumente können mit Hilfe eines Cell Arrays übergeben werden. Die """built-in-Variable""" {{{nargin}}} enthält deren Anzahl:
{{{
function s = addiere(varargin)
    if (nargin==0)
        s = 0;
    else
        s = varargin{1} + addiere(varargin{2:nargin});
    endif
endfunction
}}}

!Dynamische Verwaltung der Ergebnisliste
Ebenso ermöglicht ein Cell Array die Ausgabe dynamisch großer Ergebnisvektoren.
{{{
function varargout = zuweisen(data)
    for k=1:nargout
        varargout{k} = data(:,k);
    endfor
endfunction
}}}
Dabei kann es nützlich sein zu prüfen, ob die Größen der """Input-Variablen""" oder des """Output-Cell Arrays""" innerhalb bestimmter Toleranzgrenzen liegt:
* ''nargchk (nargin_min, nargin_max, varargin)''
/%These [[InterfaceOptions]] for customising [[TiddlyWiki]] are saved in your browser
%/
Your username for signing your edits. Write it as a [[WikiWord]] (eg [[JoeBloggs]])

<<option txtUserName>>/%
<<option chkSaveBackups>> [[SaveBackups]]
<<option chkAutoSave>> [[AutoSave]]%/
<<option chkRegExpSearch>> [[RegExpSearch]]
<<option chkCaseSensitiveSearch>> [[CaseSensitiveSearch]]
<<option chkAnimate>> [[EnableAnimations]]
/%
----
Also see [[AdvancedOptions]]%/
<<plugins>>
! Überblick
Die """QR-Zerlegung""" verwendet orthogonale Matrizen zur Zerlegung von A und ist numerisch stabiler als die """LR-Zerlegung""". Zur Erstellung der orthogonalen Transformationsmatrix Q aus A kann die Householdertransformation verwendet werden. Sie bezeichnet die Spiegelung eines Vektors v an der Hyperebene durch den Ursprung. Die Hyperebene wird durch einen zu ihr orthogonalen Vektor (Normalenvektor) definiert, der wiederum aus dem Vektor v, der gespiegelt werden soll, über seinen vervielfachten Einheitsvektor abgeleitet wird. ''Deswegen kann man einfach sagen: "Man spiegelt einen Vektor v", da alle Spiegelungsbedingungen aus v folgen.''

Ziel ist die Zerlegung einer beliebigen m×n-Matrix A:
: A = QR
Wobei R eine rechte obere Dreiecksmatrix und Q eine entsprechende orthogonale Transformationsmatrix aus ℝ^^m×m^^ ist. Durch die Householdertransformation lässt sich A sukzessive eliminieren (durch sogenannte orthogonale Transformationen) und Q^^T^^ dabei stückweise aufbauen. Q^^T^^ selber wird dargestellt als das Produkt sogenannter Householdermatrizen H~~i~~ mit 1 <= i <= m-1.

! Methode
Die """QR-Zerlegung""" lässt sich umschreiben als:
: Q^^T^^A = R
Das folgende Verfahren gewinnt nach schrittweiser Eliminierung alle Householdermatrizen H~~i~~, deren Produkt Q^^T^^ ist, und die Restmatrix in Dreiecksgestallt R:
: H~~1~~ × H~~2~~ × ... × H~~m-1~~ × A = R
Für die Berechnung von H~~i~~ gilt:
: H~~i~~ = I - (2/u^^T^^u) × (uu^^T^^)
Wobei für den Householdervektor u gilt:
: u = v + (σ × ||v|| × e~~i~~)
Der Householdervektor besteht aus:
: v : Aktuelle Spalte der Matrix A
: v~~i~~ : Aktuelles Pivotelement (in aktueller Spalte v)
:: σ ist +1, falls v~~i~~ >= 0, und -1, falls v~~i~~ < 0.
: e~~i~~ : Einheitsvektor, enthält an i-ter Stelle den Wert 1, sonst 0
Durch diese orthogonalen Transformationen wird jeder Spaltenvektor von A auf das Vielfache des jeweiligen Einheitsvektors abgebildet. Zu beachten ist, dass bei jedem Eliminationsschritt nur die aktuelle Teilmatrix betrachtet wird, dh. v~~i~~ enthält bis zur i-ten Stelle nur Nullen.
; Anmerkung:
> Der Nenner u^^T^^u (Skalarprodukt bzw. quadrierte 2-Norm von u (||u||^^2^^) dient dazu, den Orthogonalvektor u auf die Länge 1 zu normieren. Wenn u bereits der Normalenvektor der Spiegelungsebene ist (also der auf Länge 1 normierte Orthogonalvektor), vereinfacht sicht die Formel zu:
> H~~i~~ = I - 2uu^^T^^
> Damit ist allerdings in der Praxis nicht zu rechnen.

! Die Bedeutung des vervielfachten Einheitsvektors
Zur Wiederholung: Jede Spalte von A soll auf das Vielfache ihres entsprechenden Einheitsvektors gespiegelt werden. Der Einheitsvektor enthält nur einen einzigen Eintrag 1 an der Stelle i des aktuellen Eliminationsschrittes i, also quasi an der Pivotstelle.
Einfaches zweidimensionales Beispiel: Erster Eliminationsschritt einer Matrix A. Die erste Spalte v soll abgebildet (gespiegelt) werden auf den vervielfachten Einheitsvektor ||v||e~~1~~:
[img[http://www.cip.ifi.lmu.de/~kaumanns/matrixmethoden/img/hh_1.png]] [1]
Der vervielfachte Einheitsvektor ist genau der Vektor, denn wir als Ergebnis unserer Elimination haben möchten, denn er enthält unterhalb der Pivotstelle nur Nullen. Zusätzlich enthält er in diesem frühen Stadium auch oberhalb der Pivotstelle nur Nullen. Diese Stellen werden jedoch später durch die Multiplikation aller H~~i~~ aufgefüllt.

Die Householdermatrix H~~1~~ soll diese Abbildung (Spiegelung) kodieren. Die Spiegelungsebene E~~v~~ wird durch v indirekt festgelegt. Definiert wird eine Hyperebene generell durch ihren Orthogonalvektor v. Dieser ist wird berechnet durch:
: u = v - ||v||e~~1~~
Der Householdervektor u bildet die Grundlage für die Householdermatrix H~~i~~. Bei der Transformation der gesamten Matrix A wird jeder andere Spaltenvektor wird an der durch den ersten Spaltenvektor definierten Hyperebene gespiegelt.
[img[http://www.cip.ifi.lmu.de/~kaumanns/matrixmethoden/img/hh_2.jpg]] [2]
Die eliminierte Matrix ist nun für den nächsten Transformationsschritt bereit, für den ein neuer Householdervektor u berechnet wird (im Bildbeispiel anhand des Vektors b'~~2-n~~).


! Beispiel
Die erste Spalte der 6x6-Matrix A soll mit einer Spiegelung H~~1~~ auf das Vielfache des ersten Einheitsvektors gespiegelt werden. Dadurch werden alle Elemente unterhalb des ersten Pivotelements eliminiert. Die hierzu benötigte Transformationsmatrix wird unsere erste Householdermatrix H~~1~~:
: H~~1~~A = A'
Iterativ wird nun mit A' fortgefahren, bis die Restmatrix nur noch aus einer oberen Dreiecksmatrix R besteht:
: H~~2~~A' = A"""''"""
: H~~3~~A"""''""" = A"""'''"""
: H~~4~~A"""'''""" = A"""''''"""
: H~~5~~A"""''''""" = R
Die Transformationsmatrix Q^^T^^ ist das Produkt aller Householdermatrizen:
: Q^^T^^ = H~~1~~ H~~2~~ H~~3~~ H~~4~~ H~~5~~

Numerische Beispielrechnungen siehe [[Schütz, FHTW Berlin|http://www.bachelorme.de/mathe/vortrag_schuetz17_05_2006.pdf]] und [[Urban, FHTW Berlin|http://byrlin.de/master/nm/vortraege/Householder_Transformation_Kamilla_Urban.pdf]].

Bildnachweis:
[1] http://byrlin.de/master/nm/vortraege/Householder_Transformation_Kamilla_Urban.pdf
[2] http://www.pnas.org/content/102/11/4045/suppl/DC1
http://www.mpi-inf.mpg.de/departments/d1/teaching/ss10/MFI2/kap47.pdf
Kursmaterial zum Hauptseminar 2010/2011, Prof. Dr. Klaus Schulz
Matrixmethoden in Textmining
http://www.cip.ifi.lmu.de/~kaumanns/matrixmethoden/index.html
Skripte sind ausgelagerter Programmcode, kurz gesagt. Durch die Methode {{{source('Dateiname')}}} werden sie von der Kommandozeile, der Shell oder von einem anderen Skript aus geladen und geparst, dh. der enthaltende Code wird ausgeführt. Jedes Skript kann außerhalb der """Octave-Eingabeaufforderung""" in der Shell durch "octave skriptname" aufgerufen werden. Skripte dürfen nicht mit {{{function}}} beginnen, da sie sonst als Module interpretiert werden. Variablen, die innerhalb von Skripten initialisiert werden, befinden sich auf der gleichen Gültigkeitsebene wie der Skriptaufruf. Mit Hilfe von Skripten ist es möglich, Funktionen zu laden, ohne sie auszuführen. Beispiel:
{{{
# Skriptbeispiel
1;
function foo(x)
    bar(x);
endfunction

function bar(x)
    x = 1;
endfunction
}}}
Obwohl die Funktion {{{bar()}}} erst nach ihrem ersten Aufruf definiert wird, wirft Octave keine Fehlermeldung, da Referenzen erst beim Aufruf überprüft werden.
<<list all>>
# 18.10.2010<br>''Vorbesprechung, Themenvergabe''<br><br>
# 25.10.2010<br>''Kapitel 1,2: Einführung Vektoren und Matrizen'' (Bakiu)<br><br>01.11.2010<br>//Feiertag//<br><br>
# 08.11.2010<br>''Kapitel 3: Lineare Gleichungssysteme'' (Schulz & Kaumanns)<br><br>
# 15.11.2010<br>''Einführung in Octave'' (Kaumanns)<br><br>
# 22.11.2010<br>''Kapitel 3: Lineare Gleichungssysteme, Methode der kleinsten Quadrate'' (Söhlemann)<br><br>
# 29.11.2010<br>''Kapitel 4: Orthogonalität'' (Peters)<br><br>
# 06.12.2010<br>''Kapitel 5: Dekomposition 1: """QR-Dekomposition"""'' (Dillmann)<br><br>
# 13.12.2010<br>''Kapitel 6: Dekomposition 2: """Singular Value Decomposition"""'' (Galgóczy & Bildner)<br><br>
# 20.12.2010<br>''Latent Semantisches Indexieren'' (Galgóczy & Bildner)<br><br><hr>//Julferien//<hr><br><br>
# 10.01.2011<br>''Octave und LSI'' (Kaumanns)<br><br>
# 17.01.2011<br>''Page Ranking'' (Stangenberger)<br><br>
# 24.01.2011<br>''Keyword und Keysentence Extraction'' (Gadelrab)<br><br>
# 31.01.2011<br>''Seidel Magisterarbeit und Dissertation'' (Erhartitsch)<br><br>
# 07.02.2011<br>''Schlussbesprechung''
"""Octave-Variablen""" sind schwach-dynamisch typisiert und werden damit zur Laufzeit mit ihren jeweiligen Datentypen initialisiert und bei Bedarf implizit umgewandelt. Eine Deklaration ist nicht notwendig, außer es bestehen besondere Anforderungen an ihre Lebenszeit.

!Globale Variablen
Globale Variablen können mit dem Schlüsselwort {{{global}}} deklariert werden:
{{{
global x;
}}}
Um auf eine globale Variable innerhalb einer Funktion zugreifen zu können, muss sie importiert werden, ähnlich wie in PHP:
{{{
global x;
function f()
    global x;
    x = 1;
endfunction
}}}
Nützliche Funktionen:
* ''isglobal(x)'': Ob eine Variable global ist

!Persistente Variablen
Wenn eine Variable nur lokal gültig sein soll (dh. im Skopus einer bestimmten Funktion), deklariert man sie mit dem Schlüsselwort {{{persistent}}}. Die Variable lebt dann so lange, wie die Funktionsdeklaration im Speicher bleibt, dh. bis zum Aufruf von {{{clear}}} im """Octave-Prompt""".
{{{
function count_calls ()
       persistent calls;
       if (isempty (calls))
         calls = 0;
       endif
       printf ("'count_calls' has been called %d times\n", ++calls);
endfunction
}}}
!Matrixgenerierung
* ''eye''
: Identitätsmatrix
* ''zeros''
: Nullmatrix
* ''ones''
: Matrix aus Einsen
* ''rand''
: Matrix aus zufälligen Zahlen
* ''diag''
: Diagonalmatrix

!Werte extrahieren
* ''diag''
: Mit Matrix im Argument: extrahiert Diagonale und speichert sie in Spaltenvektor
* ''inv''
: Gibt Inverse zurück
* ''pinv''
: Gibt Pseudoinverse zurück
* ''det''
: Gibt Determinante zurück
* ''rank''
: Gibt Rang zurück

!Methoden anwenden
* ''rref''
: Wendet Gauß'sche Elimination an
* ''lu''
: Wendet """LU-Decomposition""" an
* ''qr''
: Wendet """QR-Decomposition""" an
* ''ols(A,b)''
: Wendet Methode der kleinsten Quadrate für Ax=b an
Hier findet ihr Informationen und Material zum Seminar.
!Kursdetails
* Zeit: 18.10.2010 bis 07.02.2011
: Montag 10:00 bis 12:00 c.t.
* Raum: Schellingstr. 3 (S) - 244
!Kursbeschreibung
Im Bereich des Information Retrieval und Data Mining werden in den letzten Jahren vermehrt Methoden der linearen Algebra eingesetzt, um Zusammenhänge in den Daten zu erfassen und für Anwendungen nutzbar zu machen. Paradebeispiel ist die Singulärwertzerlegung, die in vielen Zusammenhängen anwendbar ist. Im Seminar werden zunächst ausführlich die mathematischen Grundlagen der Verfahren erklärt.
Der zweite Teil beschäftigt sich dann mit Anwendungen wie semantischer Indexierung, Websuche, """Keyword-Extraktion""" und anderen. //Schulz//
!Voraussetzungen
Einfache mathematische Grundbegriffe werden vorausgesetzt.
!Themen zur Hausarbeit
#Key Word/ Key Sentence Extraction (mit überwachter Householdertransformation)
#LSI mit """Baseline-Vergleich""" (siehe Elden, Kapitel 11.2.1) auf """Tf-Idf-Basis"""
#"""PageRank""" und HITS: Implementation
#"""Sparse-Matrizen""": Recherche, Implementation, Vergleich
!Literatur
* Lars Elden: ''Matrix Methods in Data Mining and Pattern Recognition'', Society for Industrial and Applied Mathematics (Siam), Philadelphia, 2007, ISBN 978-0-898716-26-9.
* Gilbert Strang: ''Lineare Algebra'', Springer Verlag Berlin, 2003 -> besonders Seite 28 bis 57
<<tiddler SiteTitle>> - <<tiddler SiteSubtitle>>
{{{
#!/usr/bin/perl

# Author: David Kaumanns
# Date: 29.12.2010
# Call: perl build_query_matrix.perl -t -s stopwords.txt -m tf_set1_matrix.csv -q q1.txt -n q1
# Call: perl build_query_matrix.perl -t -m tf_set2_matrix.csv -q q2.txt -n q2
# Needs: Stop word file, directory with document files

use warnings;
use strict;
use feature 'say';
use Getopt::Long;

$/ = undef;
my %stopwords;
my %td_tokens;
my %tf;


################################################################################
# PARSE OPTIONS
################################################################################

our $use_tf = 1;
our $queryfile = 'q1.txt';
our $outfile = 'q1';
our $stopwordfile = '';
our $td_file = 'tf_set1_matrix.csv';

GetOptions( 't'     => \$use_tf,
            'tf'    => \$use_tf,
            'i'     => sub { $use_tf = 0 }, 
            'tfidf' => sub { $use_tf = 0 },
            'm=s'   => \$td_file,
            'q=s'   => \$queryfile,
            'n=s'   => \$outfile,
            's=s'   => \$stopwordfile,
            'h'     => sub { print_help() });

if ($use_tf) {
    $outfile = 'tf_' . $outfile . '_matrix.csv';
    say "Mode:\t\tTerm frequency (tf)";
}
else {
    $outfile = 'tfidf_' . $outfile . '_matrix.csv';
    say "Mode:\t\tTerm frequency-inverse document frequency (tf-idf)";
}


################################################################################
# MAIN
################################################################################

say "Td matrix file:\t$td_file";
say "Query file:\t$queryfile";
say "Outfile:\t$outfile";

load_stopwords(\%stopwords);

get_tokens(\%td_tokens);

get_tf_data(\%tf, \%td_tokens, \%stopwords);

generate_csv_file(\%tf);

say "Done.";


################################################################################
# SUBFUNCTIONS
################################################################################

sub load_stopwords {
    my $stopwords_ref = shift;
    
    open(STOPWORDS, $stopwordfile);
    
    map { $stopwords_ref->{$_} = 1; } split(/\n/, <STOPWORDS>) if $stopwordfile;
    
    close(STOPWORDS);
}

################################################################################
sub get_tokens {
    my $token_ref = shift;
    
    open(TD, $td_file);
    
    my $data = <TD>;
    while ($data =~ /\n(.+?),/g) {
        $token_ref->{$1} = 1;
    }
    
    close(TD);
}

################################################################################
sub get_tf_data {
    my $tf_ref = shift;
    my $td_tokens_ref = shift;
    my $stopwords_ref = shift;
    
    map { $tf_ref->{$_} = 0; } keys %{$td_tokens_ref};
    
    open(IN, $queryfile);

    foreach (split(/[\W0-9]+/, <IN>)) { # For each token...
        if ($td_tokens_ref->{$_}) { # Ignore query tokens that do not occur in the document set
            $_ = lc($_);
            
            # Count term frequencies
            $tf_ref->{$_}++ if !$stopwords_ref->{$_};
        }
    }
    
    close(IN);
}

################################################################################
sub generate_csv_file {
    my $tf_ref = shift;
    
    open(OUT,'>',$outfile);
    
    say OUT ',' . $queryfile;
    map { say OUT $_ . ',' . $tf_ref->{$_} } sort keys %{$tf_ref};
    
    close(OUT);
}

################################################################################
sub print_help {
    print("
Help:
\t-t\t\tUse Term frequencies
\t-i\t\tUse Term frequency-inverse document frequencies
\t-n [name]\tSpecify matrix name (default = $outfile)
\t-s [file]\tSpecify filename of stop word list (default = $stopwordfile)
\t-nos\t\tDisable usage of stop words
");
    exit(1);
}
}}}