Скайлайн матрицасы

Илимий эсептөөдө, Skiline матрицасын сактоо же SKS, же өзгөрүлмө тилке матрицасын сактоо, же конверт сактоо схемасы-бул матрицанын сакталуу талабын тилкелүү сактоого караганда көбүрөөк азайтуучу сейрек матрица сактоо форматы матрицасынын бир түрү. Тилкелүү сактагычта диагоналдан (жарым тилке туурасы деп аталат) белгиленген аралыктагы бардык жазуулар сакталат. Колоннага багытталган асман тирегиндеги сактагычта ар бир тилкедеги биринчи нөлдөн башка жазуудан акыркы нөлдөн башка жазууга чейинки жазуулар гана сакталат. Ошондой эле, саптарга багытталган асман тиреген сактагыч бар жана симметриялуу матрицалар үчүн, адатта, бир гана үч бурчтук сакталат.

Мамычага багытталган skyline матрицасы (жогорку жакта). Төмөндө салыштырмалуу сактоо түзүмү болуп саналат. Аты нөл эмес жогорку баалуулуктардын асман тиреген асман сызыгына окшоштугунан келип чыккан.

Скайлайнды сактоо структуралык механиканын чексиз элементтик коддорунда абдан популярдуу болуп калды, анткени асман сызыгы Чолескинин бузулушу менен сакталат (симметриялуу, оң аныкталган матрица менен сызыктуу теңдемелер системаларын чечүү ыкмасы; бардык толтуруу асман сызыгына кирет), ал эми чексиз элементтердин теңдемелер системалары салыштырмалуу кичинекей асман сызыгына ээ. Мындан тышкары, skyline Cholesky коддоо аракети Cholesky үчүн тилкелүү матрицалар үчүн бирдей (тилкелүү матрицалар үчүн жеткиликтүү, мисалы, LAPACK; skyline кодунун прототиби үчүн, караңыз ).

Матрицаны асман сызыгы форматында сактоодон мурун, саптар жана тилкелер, адатта, асман сызыгынын көлөмүн азайтуу (сакталган нөлдөн башка жазуулардын саны) жана асман сызыгындагы операциялардын санын азайтуу үчүн кайра номурланат Чолески алгоритми. Ошондой эле, ошол эле эвристикалык номерирлөө алгоритми, ал тилке туурасын азайтат, ошондой эле асман тирегин азайтуу үчүн колдонулат. Негизги жана эң алгачкы алгоритмдердин бири–бул тескери Катилл-Макки алгоритми.

Бирок, Асман сызыгын сактоо өтө чоң системалар үчүн анчалык популярдуу эмес (миллиондогон теңдемелер), анткени асман сызыгы Чолески массалык параллель эсептөө үчүн оңой эле ылайыкташа албайт жана матрицанын нөлдөн башка жазууларын гана сактаган жалпы сейрек ыкмалар, толтуруунун аздыгынан улам, өтө чоң көйгөйлөр үчүн натыйжалуу болуп калат.

Ошондой эле караңыз

• Сейрек матрица
• Band матрицасы
• Frontal чечүүчү

Шилтемелер

1. Watkins, David S. (2002), Fundamentals of matrix computations (Second ed.), New York: John Wiley & Sons, Inc., p. 60, ISBN 0-471-21394-2 
2. Barrett, Richard; Berry; Chan; Demmel; Donato; Dongarra; Eijkout; Pozo; Romine; Van der Vorst (1994), "Skyline Storage (SKS)", Templates for the solution of linear systems, SIAM, ISBN 0-89871-328-5 
3. George, Alan; Liu, Joseph W. H. (1981), Computer solution of large sparse positive definite systems, Prentice-Hall Inc., ISBN 0-13-165274-5 . The book also contains the description and source code of simple sparse matrix routines, still useful even if long superseded.
4. Duff, Iain S.; Erisman, Albert M.; Reid, John K. (1986), Direct methods for sparse matrices, Oxford University Press, ISBN 0-19-853408-6