www.wikidata.uk-ua.nina.az

Розріджена матриця матриця більша частина елементів якої є нулі Матрицю в якої більшість елементів не дорівнюють нулю на

Розріджена матриця

Розріджена матриця — матриця, більша частина елементів якої є нулі. Матрицю, в якої більшість елементів не дорівнюють нулю називають щільною.

Немає єдиного визначення, яка кількість ненульових елементів має бути в матриці, щоб вона була розрідженою. Для матриці порядку n елементів кількість ненульових елементів:

  • є O(n). Таке визначення підходить хіба для теоретичного аналізу асимптотичних властивостей матричних алгоритмів.
  • в кожному рядку не перевищує 10 в типовому випадку.
  • обмежено , де .

Застосування Редагувати

Величезні розріджені матриці часто виникають, наприклад, при чисельному розв’язуванні диференціальних рівнянь у частинних похідних.

Представлення у структурах даних Редагувати

Зберігати цілу матрицю у пам'яті комп'ютера є неефективно по відношенню до пам'яті, тому є альтернативні способи збереження таких матриць.

Зберігання ненульових елементів Редагувати

Одним з таких способів полягає в зберіганні ненульових елементів та їх координат. Цей спосіб є економний для пам'яті але для виконання дій з матрицями (додавання, множення) він є неефективний, оскільки кожного разу потрібно перебирати всі елементи для пошуку відповідного елемента.

Зберігання ненульових елементів зв'язаних вказівниками Редагувати

У цьому способі збереження кожен ненульовий елемент зберігається у вигляді значення, номера рядка та стовпця і вказівника на наступний елемент в рядку і стовпці. Для цього методу збереження потрібно також зберігати рамку, яка складається з таких самих елементів, до якої ми будемо прив'язувати всі елементи вказівниками. Цей спосіб потребує більше пам'яті, але при цьому збільшується швидкість виконання дій над матрицями.

Бібліотеки програм Редагувати

  • SparseLib++ (C++)
  • uBLAS (C++, в скад Boost)
  • SPARSPAK (Fortran)
  • CSparse (C)

Примітки Редагувати

  1. Писсанецки, 1988, Введение
  2. SparseLib++
  3. uBLAS / Boost
  4. 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. — ISBN 978-1-4503-0245-6. — DOI:10.1145/1057931.1057933
  5. T. A. Davis, Direct Methods for Sparse Linear Systems, SIAM, Philadelphia, September 2006

Література Редагувати

  • Reginald P. Tewarson Sparse Matrices. — Academic Press, 1973. — 160 с. — ISBN 0126856508 перевод: Тьюарсон Р. Разреженные матрицы = Sparse Matrices. — М.: Мир, 1977. — 191 с.
  • Писсанецки С. Технология разреженных матриц = Sparse Matrix Technology. — М.: Мир, 1988. — 410 с. — ISBN 5-03-000960-4
  • Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений = Computer Solution of Large Sparse Positive Definite Systems. — М.: Мир, 1984. — 333 с.
В іншому мовному розділі є повніша стаття Sparse matrix(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою перекладу з англійської. (червень 2017)
  • Дивитись автоперекладену версію статті з мови «англійська».
  • Перекладач повинен розуміти, що відповідальність за кінцевий вміст статті у Вікіпедії несе саме автор редагувань. Онлайн-переклад надається лише як корисний інструмент перегляду вмісту зрозумілою мовою. Не використовуйте невичитаний і невідкоригований машинний переклад у статтях української Вікіпедії!
  • Машинний переклад Google є корисною відправною точкою для перекладу, але перекладачам необхідно виправляти помилки та підтверджувати точність перекладу, а не просто скопіювати машинний переклад до української Вікіпедії.
  • Не перекладайте текст, який видається недостовірним або неякісним. Якщо можливо, перевірте текст за посиланнями, поданими в іншомовній статті.
  • Докладні рекомендації: див. Вікіпедія:Переклад.
Це незавершена стаття з математики.
Ви можете допомогти проєкту, виправивши або дописавши її.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Rozridzhena matricya matricya bilsha chastina elementiv yakoyi ye nuli Matricyu v yakoyi bilshist elementiv ne dorivnyuyut nulyu nazivayut shilnoyu Nemaye yedinogo viznachennya yaka kilkist nenulovih elementiv maye buti v matrici shob vona bula rozridzhenoyu Dlya matrici poryadku n elementiv kilkist nenulovih elementiv 1 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 Zmist 1 Zastosuvannya 2 Predstavlennya u strukturah danih 2 1 Zberigannya nenulovih elementiv 2 2 Zberigannya nenulovih elementiv zv yazanih vkazivnikami 3 Biblioteki program 4 Primitki 5 LiteraturaZastosuvannya RedaguvatiVelichezni rozridzheni matrici chasto vinikayut napriklad pri chiselnomu rozv yazuvanni diferencialnih rivnyan u chastinnih pohidnih Predstavlennya u strukturah danih RedaguvatiZberigati cilu matricyu u pam yati komp yutera ye neefektivno po vidnoshennyu do pam yati tomu ye alternativni sposobi zberezhennya takih matric Zberigannya nenulovih elementiv Redaguvati 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 Redaguvati 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 program RedaguvatiSparseLib C 2 uBLAS C v skad Boost 3 SPARSPAK Fortran 4 CSparse C 5 Primitki Redaguvati Pissanecki 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 2006Literatura RedaguvatiReginald 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 nbsp Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Otrimano z https uk wikipedia org w index php title Rozridzhena matricya amp oldid 36648011