Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 9 ] 
Автор Сообщение
 Заголовок сообщения: Вычислительно неудобный алгоритм
СообщениеДобавлено: 17 сен 2015, 11:18 
Не в сети
Начинающий
Зарегистрирован:
15 авг 2013, 09:56
Сообщений: 9
Cпасибо сказано: 1
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Подскажите пожалуйста какой алгоритм линейной алгебры, не похожий на LU/Гаусса, обладает наибольшим вычислительным неудобством с точки зрения обращений в память (нелинейная адресация элементов массива и т.п.)?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Вычислительно неудобный алгоритм
СообщениеДобавлено: 17 сен 2015, 16:22 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
27 дек 2011, 18:32
Сообщений: 2466
Откуда: Украина, Одесса
Cпасибо сказано: 565
Спасибо получено:
698 раз в 602 сообщениях
Очков репутации: 186

Добавить очки репутацииУменьшить очки репутации
Может алгоритм Якоби. Да и практически любой алгоритм для разреженных матриц.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Вычислительно неудобный алгоритм
СообщениеДобавлено: 18 сен 2015, 15:06 
Не в сети
Начинающий
Зарегистрирован:
15 авг 2013, 09:56
Сообщений: 9
Cпасибо сказано: 1
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Метод Якоби для собственных значений или для решений СЛАУ?
Для разреженных матриц нельзя.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Вычислительно неудобный алгоритм
СообщениеДобавлено: 18 сен 2015, 20:23 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
27 дек 2011, 18:32
Сообщений: 2466
Откуда: Украина, Одесса
Cпасибо сказано: 565
Спасибо получено:
698 раз в 602 сообщениях
Очков репутации: 186

Добавить очки репутацииУменьшить очки репутации
для собственных значений

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Вычислительно неудобный алгоритм
СообщениеДобавлено: 18 ноя 2015, 11:50 
Не в сети
Начинающий
Зарегистрирован:
15 авг 2013, 09:56
Сообщений: 9
Cпасибо сказано: 1
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Метод Якоби для собственных значений не подошел вот почему. Нужен алгоритм, поддающийся распараллеливанию по итерациям для его последующей реализации на конвейерном вычислительном устройстве.
Ранее таким образом было успешно реализовано LU-разложение, т.к. этот алгоритм имеет итерационную структуру и итерации информационно очень мало связаны друг с другом. Точнее, очередная ступень конвейера, вычисляющая ведущую и ведомые строки может вступать в работу как только на выходе предыдущей ступени появляются первые выходные данные.
В методе Якоби же информационная зависимость между итерациями такова, что очередная ступень конвейера должна дождаться пока предыдущая ступень полностью отработает. Таким образом, никакой параллельной работы ступеней конвейера не получается.
Подскажите пожалуйста, что какие еще алгоритмы линейной алгебры могут быть использованы по этому критерию?
В литературе, по большому счету, указываются следующие стандартные задачи линейной алгебры:
- решение СЛАУ
- задача наименьших квадратов
- задача на собственные значения
- методы вычисления сингулярного разложения
Исходя из того, что реализованное LU-разложение относится к СЛАУ, а среди задач на собственные значения вряд ли есть подающиеся конвейеризации, остаются наименьшие квадраты и сингулярное разложение. Сейчас ковыряюсь в них, но пока "тёмный лес".
Может есть какие-то наводки?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Вычислительно неудобный алгоритм
СообщениеДобавлено: 18 ноя 2015, 16:47 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
27 дек 2011, 18:32
Сообщений: 2466
Откуда: Украина, Одесса
Cпасибо сказано: 565
Спасибо получено:
698 раз в 602 сообщениях
Очков репутации: 186

Добавить очки репутацииУменьшить очки репутации
ATAG
Мы (моя группа) весной распараллеливали метод Якоби. Я посмотрю конспект.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Analitik "Спасибо" сказали:
ATAG
 Заголовок сообщения: Re: Вычислительно неудобный алгоритм
СообщениеДобавлено: 18 ноя 2015, 16:50 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
27 дек 2011, 18:32
Сообщений: 2466
Откуда: Украина, Одесса
Cпасибо сказано: 565
Спасибо получено:
698 раз в 602 сообщениях
Очков репутации: 186

Добавить очки репутацииУменьшить очки репутации
А в принципе почти все методы для разреженных матриц не очень "удобные".

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Вычислительно неудобный алгоритм
СообщениеДобавлено: 18 ноя 2015, 16:57 
Не в сети
Начинающий
Зарегистрирован:
15 авг 2013, 09:56
Сообщений: 9
Cпасибо сказано: 1
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Спасибо!
Скорее всего распараллеливание велось внутри итерации по данным? Потому что для кластеров применяется именно этот вид распараллеливания. Каждому процессору - свой кусок задачи.
У меня несколько другая цель - сделать конвейерный спец.вычислитель, который возможен только в случае распараллеливания по итерациям - каждой ступени конвейера - своя очередная итерация. И если ступень ждет, когда полностью отработает предыдущая итерация - параллельной работы не получится. А внутри итерации Якоби распараллеливается, это да.
В данном случае важно не столько неудобство для ПК, сколько возможность конвейеризовать алгоритм.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Вычислительно неудобный алгоритм
СообщениеДобавлено: 18 ноя 2015, 17:19 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
27 дек 2011, 18:32
Сообщений: 2466
Откуда: Украина, Одесса
Cпасибо сказано: 565
Спасибо получено:
698 раз в 602 сообщениях
Очков репутации: 186

Добавить очки репутацииУменьшить очки репутации
ATAG

Ок. Тогда мой вариант отпадает.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 9 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Алгоритм

в форуме Дискретная математика, Теория множеств и Логика

Ilonka66

1

423

01 апр 2015, 17:08

Алгоритм

в форуме Информатика и Компьютерные науки

smirnyaga

1

416

14 фев 2015, 18:51

Алгоритм Левинсона

в форуме Численные методы

meiblorn

0

369

14 июн 2015, 21:29

KJI-Алгоритм LU-разложения

в форуме Численные методы

MyOwnSurgery

0

198

20 апр 2020, 22:16

Алгоритм ARFIMA

в форуме Математическая статистика и Эконометрика

k010101bit

4

532

26 янв 2020, 01:21

Алгоритм Кэннона

в форуме Информатика и Компьютерные науки

Eva59

0

455

26 мар 2016, 10:20

Алгоритм Краскала

в форуме Дискретная математика, Теория множеств и Логика

adssfcs

1

98

16 янв 2020, 20:55

Алгоритм RANSAC

в форуме Численные методы

germ9c

1

1002

25 фев 2016, 18:52

Есть ли алгоритм?

в форуме Ряды

ZER

0

234

24 фев 2019, 13:36

Алгоритм Дейкстры

в форуме Дискретная математика, Теория множеств и Логика

Aandrew

4

123

14 май 2022, 19:18


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 7


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved