Compressed Row Storage

Compressed Row Storage

Compressed Row Storage (CRS) oder Compressed Sparse Row (CSR) ist ein häufig genutztes Verfahren zum Speichern dünnbesetzter Matrizen. In der numerischen Mathematik bezeichnet man damit eine Matrix, bei der so viele Einträge aus Nullen bestehen, dass es sich lohnt, dies auszunutzen.

Beim CRS-Verfahren werden nur die von Null verschiedenen Einträge einer (mxn)-Matrix A gespeichert: In Form eines Arrays val, also an aufeinanderfolgenden Stellen im Speicher. Die für die Abbildung zwischen Positionen in der Matrix und dem Array val benötigten Informationen werden in zwei weiteren Arrays rowPtr und colInd gespeichert. In colInd ist zu jedem Eintrag aus val der Index seiner Spalte gespeichert. Er umfasst daher gleich viele Elemente wie val. Die Werte in rowPtr legen fest, welche Werte von val zu welcher Zeile gehören.

Der formale Zusammenhang zwischen der Matrix A und ihrer Darstellung unter Verwendung von CRS lautet:

A_{i,j} =val[k] \iff (colInd[k] = j ) \and ( rowPtr[i] \leq k < rowPtr[i+1] ).

Beispiel:

A=
  \begin{pmatrix} 
    10 & 0 & 0 & 12 & 0 \\ 
    0 & 0 & 11 & 0 & 13 \\
    0 & 16 & 0 & 0 & 0 \\
    0 & 0 & 11 & 0 & 13 \\
  \end{pmatrix}

In diesem Beispiel sind in diesen 3 Vektoren folgende Werte gespeichert:


  \begin{matrix} 
    val    &=   & (10 & 12 & 11 & 13 & 16 & 11 & 13) \\
    colInd &= & (1  & 4  & 3  & 5  & 2  & 3    & 5) \\
    rowPtr &= & (0  & 2  & 4  & 5  & 7)  &     &
  \end{matrix}

Es enthalten val sowie colInd je 7 Elemente (entspricht immer Anzahl der Nichtnullelemente in A) und rowPtr 5 Elemente (entspricht immer der Anzahl Reihen in A plus 1).

Die Rekonstruktion der vollständigen Matrix aus der komprimierten Speicherform geschieht folgendermaßen: Der Wert 0 des Vektors rowPtr zeigt an, dass an der 1. Stelle der Vektoren val und colind eine neue Zeile beginnt. (Die erste Position in Vektoren hat in Computersprachen i.d.R. den Index 0.) Diese hat die von 0 verschiedenen Elemente 10 in der 1. Spalte und 12 in der 4.Spalte. An der 3. Position (Vektor-Index 2, siehe rowPtr) beginnt die nächste Zeile mit den Elementen 11 in Spalte 3 und 13 in Spalte 5 usw.

Literatur


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Dünnbesetzte Matrix — Besetzungsstruktur einer dünnbesetzten Matrix aus einer Finite Elemente Rechnung, Nichtnulleinträge erscheinen in Schwarz In der numerischen Mathematik bezeichnet man als dünnbesetzte oder schwachbesetzte Matrix eine Matrix, bei der so viele… …   Deutsch Wikipedia

  • CRS — Die Abkürzung CRS steht für: Carrier Routing System, ein von Cisco entwickelter Router Centrum für religiöse Studien, siehe Westfälische Wilhelms Universität in Münster Chemische Referenzsubstanz, herausgegeben durch das Europäisches Direktorat… …   Deutsch Wikipedia

  • Comparison of MySQL database engines — This a comparison between the two primary database engines (InnoDB and MyISAM) for the MySQL database management system (DBMS). A database engine (or storage engine ) is the underlying software component that a DBMS uses to create, read, update… …   Wikipedia

  • Sybase IQ — Sybase IQ, formally Sybase Adaptive Server IQ, is a relational database software system used for data warehousing, produced by the Sybase corporation.FeaturesAs a column oriented DBMS, Sybase IQ stores data tables as sections of columns of data… …   Wikipedia

  • BMP file format — Windows Bitmap Filename extension .bmp or .dib Internet media type image/x ms bmp (unofficial) or image/x bmp (unofficial) Type code BMP BMPf BMPp Uniform Type Identifier com.microsoft.bmp …   Wikipedia

  • Sparse matrix — A sparse matrix obtained when solving a finite element problem in two dimensions. The non zero elements are shown in black. In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros (Stoer Bulirsch 2002,… …   Wikipedia

  • printing — /prin ting/, n. 1. the art, process, or business of producing books, newspapers, etc., by impression from movable types, plates, etc. 2. the act of a person or thing that prints. 3. words, symbols, etc., in printed form. 4. printed material. 5.… …   Universalium

  • information processing — Acquisition, recording, organization, retrieval, display, and dissemination of information. Today the term usually refers to computer based operations. Information processing consists of locating and capturing information, using software to… …   Universalium

  • MPEG-1 — Moving Picture Experts Group Phase 1 (MPEG 1) Filename extension .mpg, .mpeg, .mp1, .mp2, .mp3, .m1v, .m1a, .m2a, .mpa, .mpv Internet media type audio/mpeg, video/mpeg Developed by ISO, IEC Type of format audio, vid …   Wikipedia

  • Alternative fuel vehicle — refers to a vehicle that runs on a fuel other than traditional gasoline or diesel; any method of powering an engine that does not involve solely petroleum (e.g. electric car, gasoline electric hybrid, solar powered). Due to a combination of heavy …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”