რამდენი ნულია მეჩხერ მატრიცაში?

ავტორი: კობა გელაშვილი
საკვანძო სიტყვები: მეჩხერი მატრიცა, შეუღლებულ გრადიენტთა მეთოდი
ანოტაცია:

მოხსენება ეძღვნება შეუღლებული გრადიენტების (შემოკლებით CG) მეთოდის მიერ გამოყენებულ მართკუთხა მატრიცაში ნულების პროცენტული რაოდენობის განსაზღვრას, რომლის ზემოთაც მატრიცა შეგვიძლია ჩავთვალოთ მეჩხერად. ნულების პროცენტული რაოდენობის დასადგენად, რომლის ზემოთაც CG-მეთოდი jnz-ფორმატით უფრო სწრაფია ვიდრე მართკუთხა წარმოდგენით, ჩატარებდა ექსპერიმენტები (იხ. https://github.com/vakho10/Sparse-Storage-Formats). განსხვავებული ზომის 15 მატრიცა (სტრიქონების რაოდენობა n იცვლება 100 დან 1500-ის ჩათვლით, 100-ის ბიჯით) იქნა გამოყენებული. ყოველი n-ისთვის, აგებულ იქნა სიმეტრიული მატრიცები შემთხვევითი მონაცემებით, ნულების შემდეგი პროცენტით: 15, 20, 25, 30 და 35. მთლიანობაში 75 მატრიცა. მატრიცათა ზომების შესაბამისი ვექტორებიც შემთხვევითად იქნა გენერირებული. მატრიცა-ვექტორის ყოველი წყვილისთვის გაშვებულ იქნა CG-მეთოდი. ნულების 35%-ის შემთხვევაში, ტესტების აბსოლუტურ უმეტესობაში jnz-ფორმატმა დააჩქარა სისტემის ამოხსნის პროცესი. ნულების რაოდენობის ზრდა განსხვავებას კიდევ უფრო თვალსაჩინოს ხდის. თუ გავითვალისწინებთ, რომ jnz-ფორმატი მეხსიერების დაზოგვას იწყებს ნულების 67%-ის შემთხვევაში, რჩება შთაბეჭდილება, რომ მეჩხერობის ცნება პროგრამის შესრულების დროის აზრით (განსხვავებით მეხსიერებისგან) არის საგრძნობლად სუსტი.

მიმაგრებული ფაილები:

How Many Zeros in the Sparse Matrix? [en]
რამდენი ნულია მეჩხერ მატრიცაში? [ka]