Проређена матрица

Горња проређена матрица садржи само 9 ненултих елемената, са 26 нултих елемената. Њена проређеност је 74%, а густина 26%

Пример проређене матрице

Проређена матрица добијена решавањем проблема коначних елемената у две димензије. Не-нулти елементи су приказани црном бојом.

У нумеричкој анализи и научном рачунању^[1], проређена матрица или ретки низ је матрица у којој је већина елемената нула. Не постоји строга дефиниција колико мора бити нултих елемената да би се матрица сматрала ретком, али најчешћи критеријум је да је број нултих елемената отприлике број редова или колона. Супротно томе, ако већина елемената није нула, матрица се сматра густом^[1]. Број елемената са нултом вредношћу подељен са укупним бројем елемената (нпр. m × n за m × n матрицу) понекад се назива проређеношћу матрице.

Концептуално, проређеност одговара системима са неколико упарених интеракција. На пример, замислите линију куглица повезаних опругама од једне до друге: ово је проређен систем јер се спајају само суседне лопте. Супротно томе, ако би иста линија куглица имала опруге које повезују сваку куглицу са свим осталим куглицама, систем би одговарао густој матрици. Концепт проређености је користан у комбинаторици и подручјима примене као што су теорија мрежа и нумеричка анализа, које обично имају малу густину значајних података или веза. Велике проређене матрице често се појављују у научним или инжењерским применама при решавању парцијалних диференцијалних једначина.

Приликом складиштења и манипулисања ретким матрицама на компјутеру, корисно је и често је потребно користити специјализоване алгоритме и структуре података који користе предност проређене структуре матрице. За проређене матрице су направљени специјализовани рачунари^[2], јер су оне уобичајене у пољу машинског учења^[3]. Операције уз помоћ стандардних структура и алгоритама густе матрице су споре и неефикасне када се примене на матрице великих густина, јер се процесирање и меморија троше на нуле. Распршени подаци се по природи лакше компресују и због тога захтевају знатно мање складишта. Неким врло великим ретким матрицама је немогуће манипулисати уз помоћ стандардних алгоритама густе матрице.

Складиштење проређене матрице

Матрица се обично чува као дводимензионални низ. Сваки унос у низ представља елемент ai,j матрице и њему се приступа путем два индекса i i j. Уобичајено, i је индекс реда, нумерисан од врха до дна, а j индекс колоне, нумерисан слева удесно. За m × n матрицу, количина меморије потребна за чување матрице у овом формату сразмерна је m × n (не узимајући у обзир чињеницу да димензије матрице такође треба да буду сачуване).

У случају проређене матрице, захтев за значајним смањењем меморије може се остварити складиштењем само не-нултих уноса. У зависности од броја и дистрибуције не-нултих уноса, могу се користити различите структуре података и остварити огромне уштеде у меморији у поређењу са основним приступом. Компромис је у томе што приступ појединачним елементима постаје сложенији и потребне су додатне структуре да би се једнозначно могла повратити оригинална матрица.

Формати се могу поделити у две групе:

• Они који подржавају ефикасне модификације, као што су DOK (Dictionary of keys), LIL (List of lists) или COO (Coordinate list). Они се обично користе за конструкцију матрица.
• Они који подржавају ефикасне операције приступа и матрице, као што су CSR (Compressed Sparse Row) или CSC (Compressed Sparse Column).

Речник кључева (Dictionary of keys - DOK)

DOK се састоји од речника који мапира (ред, колона)-парове са вредношћу елемента. Елементи који недостају у речнику узимају се као нула. Формат је добар за постепено конструирање проређене матрице случајним редоследом, али лош за итерацију преко не-нултих вредности у нелексикографском редоследу. Матрица се обично конструише у овом формату, а затим се конвертује у други ефикаснији формат за обраду^[4].

Списак листи (List of lists - LIL)

LIL чува једну листу по реду, при чему сваки унос садржи индекс колоне и вредност. Ти уноси се обично сортирају према индексу колоне ради бржег претраживања. Ово је још један формат који је добар за изградњу инкременталне матрице^[5].

Листа координата (Coordinate list - COO)

COO чува листу торки (ред, колона, вредност). Идеално је да се уноси сортирају прво према индексу редова, а затим према индексу колона, како би се побољшала времена насумичног приступа. Ово је још један формат који је добар за изградњу инкременталне матрице.

Компресовани проређени ред (Compressed sparse row - CSR, CRS ili Yale format)

Compressed sparse row (CSR) ili compressed row storage (CRS) ili Yale формат представљају матрицу M пута три (једнодимензионална) низа, који садрже не-нулте вредности, обим редова и индексе колона. Слично је COO-у, али су индекси редова компресовани, па отуда и назив. Овај формат омогућава брз приступ редовима и умножавање вектора и матрице (Mx). CSR формат се користи најмање од средине 1960-их, а први потпуни опис појавио се 1967. године^[6].

CSR формат чува ретку m × n матрицу M у облику реда користећи три (једнодимензионална) низа (V, COL_INDEX, ROW_INDEX). Нека NNZ означава број не-нултих уноса у M. (Имајте на уму да ће се овде користити индекси засновани на нули.)

Низови V и COL_INDEX су дужине NNZ и садрже вредности које нису нула и индексе колона тих вредности.

Низ ROW_INDEX је дужине m + 1 и кодира индекс у V и COL_INDEX одакле започиње дати ред.

Последњи елемент је NNZ, тј. фиктивни индекс у V непосредно после последњег валидног индекса NNZ - 1^[7].

На пример, матрица (5 0 0 0;0 8 0 0;0 0 3 0;0 6 0 0) јe 4x4 матрица са 4 елемента који нису нула, стога

v = [ 5 8 3 6 ]

COL_INDEX = [ 0 1 2 1 ]

ROW_INDEX = [ 0 1 2 3 4 ]

претпоставља се језик индексиран нулом.

Да би се издвојио ред, прво дефинишемо:

row_start = ROW_INDEX[row]

row_end = ROW_INDEX[row + 1]

Затим узимамо делове од V и COL_INDEX започињући у row_start и завршавајући у row_end.

Да бисмо издвојили ред 1 (други ред) ове матрице поставили смо row_start=1 и row_end=2. Затим правимо делове v[1:2]=[8] и COL_INDEX[1:2]=[1]. Сада знамо да у реду 1 имамо један елемент у колони 1 са вредношћу 8.

У овом случају CSR репрезентација садржи 13 уноса, у поређењу са 16 у оригиналној матрици. CSR формат штеди на меморији само када је NNZ < (m (n - 1) - 1) / 2. Други пример, матрица [10 20 0 0 0 0; 0 30 0 40 0 0; 0 0 50 60 70 0; 0 0 0 0 0 80] је 4x6 матрица (24 уноса) са 8 не-нултих елемената, стога v = [10 20 30 40 50 60 70 80], COL_INDEX = [0 1 1 3 2 3 4 5], ROW_INDEX = [0 2 4 7 8].

Цео ред се складишти као 21 унос.

• ROW_INDEX дели низ V у редове (10,20) (30,40) (50,60,70) (80)
• COL_INDEX поравнава вредности у колоне (10,20,...) (0,30,0,40,...) (0,0,50,60,70,0) (0,0,0,0,0,80)

Имајте на уму да је у овом формату прва вредност ROW_INDEX- а увек нула, а последња увек NNZ, тако да су они у неком смислу сувишни (иако у програмским језицима где дужина низа треба да буде експлицитно ускладиштена, NNZ не би био сувишан). Ипак, ово избегава потребу да се обрачунава изузетан случај приликом израчунавања дужине сваког реда, јер то гарантује да формула ROW_INDEX[i + 1] - ROW_INDEX[i] ради за било који ред i. Штавише, трошкови меморије овог сувишног складишта вероватно су безначајни за довољно велику матрицу.

(Стари и нови) Yale-ови формати проређене матрице су примери CSR шеме. Стари Yale формат ради тачно онако како је горе описано, са три низа; нови формат комбинује ROW_INDEX и COL_INDEX у један низ и одвојено обрађује дијагоналу матрице^[8].

За матрице логичког суседства, низ података може бити изостављен, јер је постојање уноса у низу редова довољно за моделирање односа бинарног суседства.

Ово је вероватно познато као Yale формат јер је предложен у извештају Yale Sparse Matrix 1977. године из Одељења за рачунарске науке на Yale универзитету^[9].

Компресована проређена колона (Compressed sparse column - CSC ili CCS)

CSC (http://netlib.org/linalg/html_templates/node92.html#SECTION00931200000000000000) је сличан CSR-у, осим што се вредности читају прво по колони, индекс реда се чува за сваку вредност, а складиште се и показивачи колоне. На пример, CSC je (val, row_ind, col_ptr), где је val низ (од врха до дна, а затим слева надесно) не-нултих вредности матрице; row_ind су индекси редова који одговарају вредностима; и, col_ptr је листа индекса val где свака колона почиње. Назив се заснива на чињеници да су информације о индексу колоне компресоване у односу на формат COO. Обично се користи други формат (LIL, DOK, COO) за изградњу. Овај формат је ефикасан за аритметичке операције, резање колона и матрично-векторске производе. Pogledajte scipy.sparse.csc_matrix (http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csc_matrix.html). Ово је традиционални формат за спецификацију проређене матрице у MATLAB-у (путем (https://www.mathworks.com/help/matlab/ref/sparse.html функције).

Посебне структуре

Матрица опсега

Важна посебна врста ретких матрица је матрица опсега, дефинисана на следећи начин. Доњи пропусни опсег матрице A је најмањи број p такав да унос ai,j нестаје кад год је i > j + p. Слично томе, горњи пропусни опсег је најмањи број p такав дa је ai,j = 0 кад год је i < j - p (Golub & Van Loan 1996, §1.2.1). На пример, тридијагонална матрица има доњи пропусни опсег 1 и горњи пропусни опсег 1. Као још један пример, следећа проређена матрица има и горњи и доњи пропусни опсег једнак 3. Приметите да су нуле представљене тачкама ради јасноће.

Матрице са релативно малим горњим и доњим пропусним опсегом познате су као матрице опсега и често се прилагођавају једноставнијим алгоритмима од општих ретких матрица;или се понекад може применити алгоритам густе матрице и постићи ефикасност једноставним превлачењем преко смањеног броја индекса.

Преуређивањем редова и ступаца матрице А може бити могуће добити матрицу А′ са нижим пропусним опсегом. Бројни алгоритми су дизајнирани за минимизирање пропусног опсега.

Дијагонална

Веома ефикасна структура за екстремни случај матрица опсега, дијагонална матрица служи томе да се само уноси у главној дијагонали чувају као једнодимензионални низ, тако да дијагонална n × n матрица захтева само n уноса.

Симетрична

Симетрична проређена матрица настаје као матрица суседности неусмереног графа; може се ефикасно чувати као листа суседности.

Блок дијагонала

Блок-дијагонална матрица састоји се од под-матрица дуж својих дијагоналних блокова. Блок-дијагонална матрица А има облик

где је Ak квадратна матрица за све k = 1, …, n.

Смањивање попуњавања

Попуњавање матрице се односи на оне уносе који се мењају од почетне нулте вредности до вредности која није нула током извршавања алгоритма. Да би се смањили захтеви за меморијом и број аритметичких операција коришћених током алгоритма, корисно је минимизирати попуњавање пребацивањем редова и колона у матрици. Симболична Choleksy разградња може се користити за израчунавање најгорег могућег попуњавања пре него што се изврши стварна Cholesky разградња. У употреби су друге методе осим Choleksy разградње. Методе ортогонализације (као што је QR факторизација) су уобичајене, на пример, када се проблеми решавају методама најмањег квадрата. Иако је теоријско попуњавање још увек исто, у пракси се „лажне не-нуле“ могу разликовати за различите методе. А симболичке верзије тих алгоритама могу се користити на исти начин као и симболичка Cholesky разградња за израчунавање најгорих случајева попуњавања.

Софтвер

Многе софтверске библиотеке подржавају проређене матрице, и пружају решења за једначине ретких матрица. Следећи су open-source:

• SuiteSparse^[10], скуп алгоритама проређене матрице, усмерен ка директном решењу ретких линеарних система.
• PETSc, велика C библиотека, која садржи мноштво различитих решавача матрице за разне формате складишта матрице.
• Trilinos, велика C ++ библиотека, са подбиблиотекама посвећеним чувању густих и ретких матрица и решавању одговарајућих линеарних система.
• Eigen3 јe C ++ библиотека која садржи неколико решавача ретких матрица. Међутим, ниједан од њих није паралелизован.
• MUMPS (MUltifrontal Massively Parallel sparse direct Solver), написан у Fortran90, je фронтални решавач.
• DUNE, библиотека коначних елемената која такође има подбиблиотеку за проређене линеарне системе и њихово решавање.
• PaStik (http://pastix.gforge.inria.fr/).
• SuperLU (http://crd-legacy.lbl.gov/~xiaoye/SuperLU/).
• Armadillo нуди C ++ омот за BLAS и LAPACK који је лаган за употребу.
• SciPy пружа подршку за неколико формата ретких матрица, линеарну алгебру и решаваче.
• SPArse Matrix (spam) (https://cran.r-project.org/web/packages/spam/index.html) R пакет за проређене матрице.
• Wolfram језик (https://reference.wolfram.com/language/guide/SparseArrays.html) Alati za rukovanje retkim nizovima
• ALGLIB C ++ и C # библиотека са подршком проређене линеарне алгебре
• ARPACK Fortran 77 библиотека за дијагонализацију и манипулацију ретким матрицама, користећи Арнолдијев алгоритам
• SPARSE (https://www.netlib.org/sparse/) Референтни (стари) NIST пакет за (стварну или сложену) дијагонализацију проређене матрице
• SLEPc библиотека за решавање линеарних система великих размера и ретких матрица
• Sympiler (https://www.sympiler.com/), генератор кода и библиотека за специфичне домене за решавање линеарних система и проблема квадратног програмирања.

Историја

Израз проређена матрица је вероватно сковао Хенри Марковиц који је покренуо неке пионирске радове, али је затим напустио ово поље^[11].