Approximate solution of dense linear systems

摘要

Razvijena je nova numerička metoda za približno rješenje velikih linearnih sustava s punim matricama. Metoda se bazira na Fourierovoj transformaciji, ali može rabiti i druge ortogonalne i unitarne transformacije koje koncentriraju energiju u mali broj koeficijenata. Ideja je inspirirana digitalnim procesiranjem signala, gdje je filtriranje i uklanjanje nebitnih i/ili selektivnih komponenti iz spektra Fourierovih frekvencija uobičajena praksa. Procedura se sastoji u transformaciji linearnoga sustava u domenu frekvencija, gdje je moguće ukloniti najmanje značajne komponente kao čitave retke i/ili stupce što rezultira u smanjenome sustavu. Rješenje za smanjeni sustav se pronađe u domeni frekvencija, dajući transformat približnog rješenja. Inverzija transformata približnoga rješenja daje približno rješenje originalnoga sustava. Prikazani su numerički eksperimenti koji ilustriraju uporabu metode i kvalitetu približnoga rješenja za računanje vlastitih vrijednosti i vlastitih vektora na matrici 1000 puta 1000 iz kemijske teorije grafova.%A novel numerical approach for approximate solution of large linear systems of a dense type has been developed. The method is based on Fourier transform although any unitary, orthogonal transform which concentrates energy in a small number of coefficients can be used. The idea comes from digital signal processing where pruning off insignificant information from spectra or filtering of selected information in frequency domain is usual practice. The procedure is to transform the linear system from the time and space domain to the frequency domain, generating a transformed system. The least significant portions in the transformed system are deleted as the whole rows and columns, yielding a smaller pruned system. The pruned system is solved in the frequency domain, generating the transform of approximate solution. Inverting the transform of approximate solution yields the approximate solution of original system. Numerical experiments illustrating feasibility of the method and quality of the approximation for 1000 by 1000 eigenvalue problem in chemical graph theory are presented.