Розріджена матриця — матриця, більша частина елементів якої є нулі. Матрицю, в якої більшість елементів не дорівнюють нулю називають щільною.
Розріджена матриця | |
Підтримується Вікіпроєктом | |
---|---|
Протилежне | щільна матриця[d] |
Розріджена матриця у Вікісховищі |
Немає єдиного визначення, яка кількість ненульових елементів має бути в матриці, щоб вона була розрідженою. Для матриці порядку n елементів кількість ненульових елементів:
- є O(n). Таке визначення підходить хіба для теоретичного аналізу асимптотичних властивостей матричних алгоритмів.
- в кожному рядку не перевищує 10 в типовому випадку.
- обмежено , де .
Застосування
Величезні розріджені матриці часто виникають, наприклад, при чисельному розв’язуванні диференціальних рівнянь у частинних похідних.
Представлення у структурах даних
Зберігати цілу матрицю у пам'яті комп'ютера є неефективно по відношенню до пам'яті, тому є альтернативні способи збереження таких матриць.
Зберігання ненульових елементів
Одним з таких способів полягає в зберіганні ненульових елементів та їх координат. Цей спосіб є економний для пам'яті але для виконання дій з матрицями (додавання, множення) він є неефективний, оскільки кожного разу потрібно перебирати всі елементи для пошуку відповідного елемента.
Зберігання ненульових елементів зв'язаних вказівниками
У цьому способі збереження кожен ненульовий елемент зберігається у вигляді значення, номера рядка та стовпця і вказівника на наступний елемент в рядку і стовпці. Для цього методу збереження потрібно також зберігати рамку, яка складається з таких самих елементів, до якої ми будемо прив'язувати всі елементи вказівниками. Цей спосіб потребує більше пам'яті, але при цьому збільшується швидкість виконання дій над матрицями.
Бібліотеки програм
- SparseLib++ (C++)
- uBLAS (C++, в скад Boost)
- SPARSPAK (Fortran)
- CSparse (C)
Примітки
- Писсанецки, 1988, Введение
- SparseLib++
- uBLAS / Boost
- Alan George, Esmond Ng A brief description of SPARSPAK Waterloo sparse linear equations package (англ.) // ACM SIGNUM Newsletter, Volume 19 Issue 4, October 1984. — N.Y, 1984. — С. 17-20. — . — DOI:10.1145/1057931.1057933
- T. A. Davis, Direct Methods for Sparse Linear Systems, SIAM, Philadelphia, September 2006
Література
- Reginald P. Tewarson Sparse Matrices. — Academic Press, 1973. — 160 с. — перевод: Тьюарсон Р. Разреженные матрицы = Sparse Matrices. — М.: Мир, 1977. — 191 с.
- Писсанецки С. Технология разреженных матриц = Sparse Matrix Technology. — М.: Мир, 1988. — 410 с. —
- Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений = Computer Solution of Large Sparse Positive Definite Systems. — М.: Мир, 1984. — 333 с.
В іншому мовному розділі є повніша стаття Sparse matrix(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою з англійської. (червень 2017)
|
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Rozridzhena matricya matricya bilsha chastina elementiv yakoyi ye nuli Matricyu v yakoyi bilshist elementiv ne dorivnyuyut nulyu nazivayut shilnoyu Rozridzhena matricya Pidtrimuyetsya VikiproyektomVikipediya Proyekt Matematika Protilezhneshilna matricya d Rozridzhena matricya u Vikishovishi Nemaye yedinogo viznachennya yaka kilkist nenulovih elementiv maye buti v matrici shob vona bula rozridzhenoyu Dlya matrici poryadku n elementiv kilkist nenulovih elementiv ye O n Take viznachennya pidhodit hiba dlya teoretichnogo analizu asimptotichnih vlastivostej matrichnih algoritmiv v kozhnomu ryadku ne perevishuye 10 v tipovomu vipadku obmezheno n 1 g displaystyle n 1 gamma de g lt 1 displaystyle gamma lt 1 ZastosuvannyaVelichezni rozridzheni matrici chasto vinikayut napriklad pri chiselnomu rozv yazuvanni diferencialnih rivnyan u chastinnih pohidnih Predstavlennya u strukturah danihZberigati cilu matricyu u pam yati komp yutera ye neefektivno po vidnoshennyu do pam yati tomu ye alternativni sposobi zberezhennya takih matric Zberigannya nenulovih elementiv Odnim z takih sposobiv polyagaye v zberiganni nenulovih elementiv ta yih koordinat Cej sposib ye ekonomnij dlya pam yati ale dlya vikonannya dij z matricyami dodavannya mnozhennya vin ye neefektivnij oskilki kozhnogo razu potribno perebirati vsi elementi dlya poshuku vidpovidnogo elementa Zberigannya nenulovih elementiv zv yazanih vkazivnikami U comu sposobi zberezhennya kozhen nenulovij element zberigayetsya u viglyadi znachennya nomera ryadka ta stovpcya i vkazivnika na nastupnij element v ryadku i stovpci Dlya cogo metodu zberezhennya potribno takozh zberigati ramku yaka skladayetsya z takih samih elementiv do yakoyi mi budemo priv yazuvati vsi elementi vkazivnikami Cej sposib potrebuye bilshe pam yati ale pri comu zbilshuyetsya shvidkist vikonannya dij nad matricyami Biblioteki programSparseLib C uBLAS C v skad Boost SPARSPAK Fortran CSparse C PrimitkiPissanecki 1988 Vvedenie SparseLib uBLAS Boost Alan George Esmond Ng A brief description of SPARSPAK Waterloo sparse linear equations package angl ACM SIGNUM Newsletter Volume 19 Issue 4 October 1984 N Y 1984 S 17 20 ISBN 978 1 4503 0245 6 DOI 10 1145 1057931 1057933 T A Davis Direct Methods for Sparse Linear Systems SIAM Philadelphia September 2006LiteraturaReginald P Tewarson Sparse Matrices Academic Press 1973 160 s ISBN 0126856508 perevod Tyuarson R Razrezhennye matricy Sparse Matrices M Mir 1977 191 s Pissanecki S Tehnologiya razrezhennyh matric Sparse Matrix Technology M Mir 1988 410 s ISBN 5 03 000960 4 Dzhordzh A Lyu Dzh Chislennoe reshenie bolshih razrezhennyh sistem uravnenij Computer Solution of Large Sparse Positive Definite Systems M Mir 1984 333 s V inshomu movnomu rozdili ye povnisha stattya Sparse matrix angl Vi mozhete dopomogti rozshirivshi potochnu stattyu za dopomogoyu perekladu z anglijskoyi cherven 2017 Divitis avtoperekladenu versiyu statti z movi anglijska Perekladach povinen rozumiti sho vidpovidalnist za kincevij vmist statti u Vikipediyi nese same avtor redaguvan Onlajn pereklad nadayetsya lishe yak korisnij instrument pereglyadu vmistu zrozumiloyu movoyu Ne vikoristovujte nevichitanij i nevidkorigovanij mashinnij pereklad u stattyah ukrayinskoyi Vikipediyi Mashinnij pereklad Google ye korisnoyu vidpravnoyu tochkoyu dlya perekladu ale perekladacham neobhidno vipravlyati pomilki ta pidtverdzhuvati tochnist perekladu a ne prosto skopiyuvati mashinnij pereklad do ukrayinskoyi Vikipediyi Ne perekladajte tekst yakij vidayetsya nedostovirnim abo neyakisnim Yaksho mozhlivo perevirte tekst za posilannyami podanimi v inshomovnij statti Dokladni rekomendaciyi div Vikipediya Pereklad Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi