Наивное исключение Гаусса - разреженные и полные матрицы

Question

Я сейчас играю с числовыми методами в MATLAB.Я пытаюсь понять зависимость времени, необходимого для решения разреженных / полных матриц одного и того же размера, с учетом различных размеров n.

Насколько я понимаю, в целом разреженные матрицы требуют более короткого времени для решения по сравнению с полными матрицами.Однако, когда я использовал метод наивного гауссова исключения, разреженные матрицы занимали значительно больше времени для решения.Я проводил исследования в Интернете по причинам, но безрезультатно.

Таким образом, я нахожусь здесь с этим вопросом в надежде, что кто-то сможет просветить меня.Заранее спасибо !!!

Это мои графики, подготовленные для лучшего понимания моего вопроса: Разреженный

Полный

Answer 1

Современные компьютеры имеют достаточно большое количество оперативной памяти, а также довольно быстрые процессоры. В этом случае системы линейных уравнений с матрицами до нескольких тысяч столбцов / строк обрабатываются очень быстро, когда обрабатываются непосредственно как плотный , независимо от их фактической разреженности. Различие между «плотным» и «разреженным» алгоритмами становится очевидным в пользу «разреженных» алгоритмов, когда размеры матрицы увеличиваются, превышая 10000 или около того (все зависит от качества конкретного «разреженного» алгоритма, а также от свойства процессора и оперативной памяти компьютера пользователя). «Разреженные» алгоритмы имеют специальные схемы для хранения матрицы, обеспечения доступа к ее элементам, их изменения и т. Д. Эти издержки могут замедлить алгоритм решения для не очень больших матриц по сравнению с простыми реализациями для плотных матриц.