Кіріспе

Элементтерінің көпшілігі нөл болатын матрица.

Спарс матрица мысалы.

Сандық талдау және ғылыми есептеулерде, спарс матрица немесе сирек массив – элементтерінің көпшілігі нөл болатын матрица. Матрицаны сирек деп тану үшін нөлдік элементтердің үлесіне қатысты қатаң анықтама жоқ, бірақ қалыпты өлшем – нөлдік емес элементтердің саны қатарлар немесе бағандар санына шамамен тең болуы. Керісінше, егер элементтердің көпшілігі нөлден өзгеше болса, матрица тығыз деп есептеледі. Олар машиналық оқыту саласында жиі кездеседі. Үлкен сирек матрицалармен стандартты тығыз матрицалық құрылымдар мен алгоритмдерді қолдану баяу және тиімсіз, себебі нөлдерге процессорлық қуат пен жад ысырап болады. Сирек деректер өзінің табиғатынан оңай қысылады, демек, сақтау үшін әлдеқайда аз орын қажет. Кейбір өте үлкен сирек матрицаларды стандартты тығыз матрицалық алгоритмдермен өңдеу мүмкін емес.

Жапсырмалы

Шағын матрицалардың маңызды ерекше түрі – жолақты матрица, ол келесідей анықталады. "A" матрицасының төменгі жолақты ені – i > j + p болғанда ai,j мүшесінің нөлге теңесетін ең кіші сан p. Сол сияқты, жоғарғы жолақты ені – i < j − p болғанда ai,j мүшесінің нөлге теңесетін ең кіші сан p. Мысалы, үшдиагональдық матрицаның төменгі және жоғарғы жолақты ені 1-ге тең. Тағы бір мысал ретінде, төмендегі сирек матрицаның төменгі және жоғарғы жолақты ені екеуі де 3-ке тең. Нақтылық үшін нөлдер нүктелермен белгіленген. Жоғары және төменгі жолақты ені салыстырмалы түрде кішкентай матрицалар жолақты матрицалар деп аталады және көбінесе жалпы сирек матрицаларға қарағанда қарапайым алгоритмдерге ие болады; немесе кейде тығыз матрица алгоритмдерін қолдануға болады және индекстердің азайтылған саны бойынша цикл жасау арқылы тиімділікті арттыруға болады. "A" матрицасының қатарлары мен бағаналарын қайта реттеу арқылы төменгі жолақты ені бар "A"′ матрицасын алуға болады. Жолақтықты азайтуға арналған бірнеше алгоритмдер бар.

Диагональды

Жолақты матрицалардың ең шекті жағдайы – диагональ матрица үшін өте тиімді құрылым – тек басты диагональ элементтерін бір өлшемді массив ретінде сақтау болып табылады. Сондықтан, диагональдық n × n матрицаға тек n элемент қана керек.

Симметриялық

Симметриялық сирек матрица бағытталмаған графтың жабыстық матрицасы ретінде туындайды; оны жабыстық тізім түрінде тиімді сақтауға болады.

Блоктың диагоналы

Блоктық диагональдық матрица өзінің диагональдық блоктарының бойындағы субматрицалардан құралады. "A" блоктық диагональдық матрицасы мына түрде келеді:

мұнда "A"k, барлық 1 ≤ k ≤ n үшін квадрат матрица болып табылады.

Толықтыруды азайту

Матрицаның толысуы – алгоритм орындалғанда бастапқы нөлдік мәндердің нөлдік емес мәндерге ауысуымен туындайтын элементтер. Алгоритм кезінде жадқа қажетті көлемді және арифметикалық операциялар санын азайту үшін матрицадағы қатарлар мен бағандарды ауыстыру арқылы толысуды азайту пайдалы. Нақты Чолски ыдырауын жасау алдында, ең нашар толысуды есептеу үшін символдық Чолски ыдырауын қолдануға болады. Чолски ыдырау әдісінен өзге де әдістер қолданылады. Мысалы, ең кіші квадраттар әдісімен есептелген мәселелерді шешуде ортогонализация әдістері (QR факторлау сияқты) жиі қолданылады. Теориялық толысу бірдей болғанымен, практикалық тұрғыдан алғанда, әртүрлі әдістер үшін "жалған нөлдік емес" мәндері әртүрлі болуы мүмкін. Сондай-ақ, осы алгоритмдердің символдық нұсқаларын символдық Чолски сияқты ең нашар жағдайлардағы толысуды есептеу үшін пайдалануға болады.

Сырлы матрицалық теңдеулерді шешу

Итеративтік және тікелей әдістер шашыраңқы матрицаларды шешу үшін қолданылады. Итеративтік әдістер, мысалы, конъюгациялық градиент әдісі және GMRES, матрица-вектор көбейтудің жылдам есептелуін пайдаланады, мұнда матрица шашыраңқы болады. Алдын ала шарттаушыларды қолдану мұндай итеративтік әдістердің жылдам түйісуіне (конвергенциясына) елеулі үлес қосуы мүмкін.

Кілттер сөздігі (DOK)

DOK сөздіктен тұрады, ол (қатар, баған) жұптарын элементтердің мәндерімен байланыстырады. Сөздікте жоқ элементтер нөлге тең деп есептеледі. Бұл формат кездейсоқ тәртіппен сиретілген матрицаны біртіндеп құруға ыңғайлы, бірақ лексикографиялық тәртіпте нөлдік емес мәндерді қарау үшін қолайсыз. Көбінесе матрица осы форматта құрастырылады, содан кейін өңдеу үшін басқа, тиімді форматқа түрлендіріледі.

Тізімдер тізімі (LIL)

LIL әр қатарға бір тізімді сақтайды, мұндағы әр жазба баған индексі мен мәнін қамтиды. Әдетте, осы жазбалар жылдам іздеу үшін баған индексі бойынша реттелген күйде ұсталады. Бұл инкрементті матрицаны құруға қолайлы форматтың бірі.

Координаттар тізімі (COO)

COO (қатар, баған, мән) жұптарының тізімін сақтайды. Ең жақсысы, жазбалар қатар индексі бойынша, содан кейін баған индексі бойынша сұрыпталған болуы керек, бұл кездейсоқ қол жеткізу жылдамдығын арттырады. Бұл - матрицаны кезең-кезеңмен құруға ыңғайлы форматтың тағы бірі.

Сығымдалған аз бағана (CSC немесе CCS)

CSC, CSR-ға ұқсас, бірақ мәндер алдымен бағана бойынша оқылады, әр мән үшін жол индексі сақталады және бағана көрсеткіштері сақталады. Мысалы, CSC (val, row ind, col ptr) түрінде болады, мұндағы val – матрицаның нөлдік емес мәндерінің массиві (жоғарыдан төмен, содан кейін солдан оңға); row ind – мәндерге сәйкес келетін жол индекстері; ал col ptr – әр баған қай val индексінен басталатынын көрсететін тізім. Атауы бағана индексі туралы ақпараттың COO форматына қарағанда ықшамдалғандығына байланысты қойылған. Көбінесе құрылым үшін басқа форматтар (LIL, DOK, COO) қолданылады. Бұл формат арифметикалық операциялар, бағандарды бөліп алу және матрица-вектор көбейту үшін тиімді. Бұл MATLAB-та сирек матрицаны (sparse функциясы арқылы) көрсетудің дәстүрлі форматы.

Тарих

Сирету матрица терминін Гарри Марковиц ойлап тапқан болуы мүмкін, ол осы саладағы алғашқы жұмыстарды бастады, бірақ кейін осы саланы тастап кетті.