Алгоритм Слоана
vitaly333
работает с неориентированным графом. Он перенумеровывает вершины
графа , тем самым уменьшая профиль матрицы, связанной с этим графом.
Сам этот алгоритм и видимо его программная реализация на языке Фортран
приведена в статье S.W.Sloan. A Fortran program for profile and
wavefront reduction. Int. J. for Numer. Meth. in Eng., vol. 28,
2651-2679 (1989).
Этой статьи в интернете я найти не смог. Да и про сам алгоритм в
интернете практически ничего нет. Я нашел только его реализацию в
библиотеке boost.Но его код там довольно сложен и запутан и
разобраться в нем я не смог.
Хотелось бы понять сам алгоритм. В виде словесного описания по шагам
или лучше всего на небольшом примере. Если кто - нибудь знает как
работает или кто -нибудь его сам программировал помогите мне! Если у
кого -нибудь есть эта статья или ссылка на неё выложите плиз.
LG
Или ваша цель и состоит в его оценке?
Evgenii Rudnyi
> интернете практически ничего нет. Я нашел только его реализацию в
> библиотеке boost.Но его код там довольно сложен и запутан и
> разобраться в нем я не смог.
Если алгоритм уже реализован, то можно просто этим воспользоваться. Если
не секрет, почему такой вариант не подходит?
> Хотелось бы понять сам алгоритм. В виде словесного описания по шагам
> или лучше всего на небольшом примере. Если кто - нибудь знает как
> работает или кто -нибудь его сам программировал помогите мне! Если у
> кого -нибудь есть эта статья или ссылка на неё выложите плиз.
Если вы запустите поиск в Google, то вы сразу же найдете эту статью.
Только надо будет заплатить денежку. Также можно запустить поиск на
http://scholar.google.com, там вы увидите статьи, которые цитируют эту
статью. К слову сказать, в обоих случаях есть статьи доступные за
бесплатно, не сама исходная статья, но статьи где алгоритм Слоана
упоминается.
Если вам нужна сама исходная статья и вы не хотите покупать ее через
Интернет, то наиболее прямой путь это пойти в библиотеку и заказать ее
там. В 1989 году библиотеки еще получали научные журналы.
В любом случае я бы предложил, чтобы в этой дискуссионной групе
авторские права уважались.
Evgenii Rudnyi
факторе матрицы путем перестановок в исходной матрице, то я бы
рекомендовал METIS
http://glaros.dtc.umn.edu/gkhome/views/metis/
Сейчас практически все его используют. Вот на слайде 18
http://modelreduction.com/doc/teaching/eurosime/lecture2.pdf
вы найдете сравнение METIS с другими алгоритмами упорядочения
vitaly333
On 7 фев, 22:25, Evgenii Rudnyi <use...@rudnyi.ru> wrote:
> Забыл сказать. Если вы хотите уменьшить число ненулевых элементов в
> факторе матрицы путем перестановок в исходной матрице, то я бы
> рекомендовал METIS
vitaly333
On Feb 7, 7:38 pm, LG <lgromane...@mail.ru> wrote:
> А чем интересен этот алгоритм, в чем его преимущества?
> Или ваша цель и состоит в его оценке?
vitaly333
> Если алгоритм уже реализован, то можно просто этим воспользоваться. Если
> не секрет, почему такой вариант не подходит?
- пишу свой солвер на языке Java а реализован он на C++.
- в библиотеке boost Sloan Alhgoritm работает со структурами данных,
придуманными и использующимися в библиотеке boost/graph а у меня в
моей программе всё по другому реализованно
- всё таки хотелось бы самому реализовать...))
Evgenii Rudnyi
>> факторе матрицы путем перестановок в исходной матрице, то я бы
>> рекомендовал METIS
>
> Мне нужно уменьшить именно профиль а не заполнение.
Правильно я понимаю, что вы хотите использовать фронтальный алгоритм для
решения системы линейных уравнений с разряженными матрицами? Если так,
то METIS и multifrontal алгоритмы будут существенно быстрее.
Я тут чуть поискал на http://scholar.google.com. Все таки похоже, что
сам исходный алгоритм уже устарел, см. например
Multilevel Algorithms for Wavefront Reduction by Y.F. Hua and J.A. Scottb
http://epubs.cclrc.ac.uk/bitstream/237/raltr-2000031.pdf
К слову сказать, здесь ссылка на
S. W. Sloan. An algorithm for profile and wavefront reduction of sparse
matrices. International Journal for Numerical Methods in Engineering,
23:239-251, 1986.
Похоже что статья, которую вы ищите, это наверное просто реализация
алгоритма, а он сам описан в этой статье.
Также в первый ссылке говорится, что реализация алгоритма Слоана описана
в двух статьях, для которых есть препринты
G. Kumfert and A. Pothen. Two improved algorithms for envelope and
wavefront reduction. BIT, 35:1-32, 1997.
http://historical.ncstrl.org/tr/ps/icase/TR-97-33.ps
J. K. Reid and J. A. Scott. Ordering symmetric sparse matrices for small
profile and wavefront. International Journal for Numerical Methods in
Engineering, 45:1737-1755, 1999.
http://epubs.cclrc.ac.uk/bitstream/128/raltr-1998016.pdf
Evgenii Rudnyi
>> не секрет, почему такой вариант не подходит?
>
> Не подходит потому что:
> - пишу свой солвер на языке Java а реализован он на C++.
Из Явы, насколько я понимаю, можно и С++ вызывать.
> - в библиотеке boost Sloan Alhgoritm работает со структурами данных,
> придуманными и использующимися в библиотеке boost/graph а у меня в
> моей программе всё по другому реализованно
Построить транслятор данных должно быть не так уж и сложно.
> - всё таки хотелось бы самому реализовать...))
Тогда вам, конечно, надо исходную статью. На Wiley она стоит 30
долларов. Дорого, но искусство требует жертв.
А вот здесь
нельзя получать статьи?
vitaly333
>
> Правильно я понимаю, что вы хотите использовать фронтальный алгоритм для
> решения системы линейных уравнений с разряженными матрицами? Если так,
> то METIS и multifrontal алгоритмы будут существенно быстрее.
>
для решения систем линейных алгебраических уравнений и поэтому
хотелось
бы уменьшить профиль алгоритмом Слоана. Алгоритм Слоана как я понял
кроме минимизации ширины профиля ещё и уменьшает фронт, поэтому раньше
применялся во фронтальных методах так?
Естественно современные Sparse Direct Solvers и фронтальные или
мультифронтальные методы в сочетании с многоуровневым упорядочением
работают намного быстрее чем устаревшие профильные и ленточные методы
но всё таки хотелось бы реализовать именно их... Точнее их я уже
реализовал , осталось реализовать алгоритмы уменьшеня профиля и ленты.
Катхилла - Макки и обратный алгоритм Катхилла - Макии у меня уже есть
в моем солвере
Теперь хотелось бы к ним прибавить метод Слоана....
Евгений, а знаете вы ещё какие -нибудь "хорошие" методы для
уменьшения ширины ленты и/или профиля кроме вышеприведенных мною?
Теп
vitaly333
Evgenii Rudnyi
> уменьшения ширины ленты и/или профиля кроме вышеприведенных мною?
К сожалению, нет. Я сам только использую численные методы, причем в
основном на уровне библиотек.
Здесь, если вы хотите заниматься этим серьезно, хорошо было бы конечно
сделать литературный поиск. Можно, конечно, поискать в Интернете, но
лучше всего для этой цели воспользоваться специализированными базами
даннах. Для вас подошли бы ISI Web of Knowledge или INSPEC. Но они
платные и надо искать библиотеку, которая имеет подписку.
vitaly333
> Тогда вам, конечно, надо исходную статью. На Wiley она стоит 30
> долларов. Дорого, но искусство требует жертв.
хороший человек. Теперь буду разбираться в ней. Когда напишу
программу могу выложить свой код сюда если нужно..
LG
для уменьшения заполненности профиля. Это просто реализовать и можно
получить лучший результат, чем с помощью, например, RCM.
Evgenii Rudnyi
> хороший человек. Теперь буду разбираться в ней. Когда напишу
> программу могу выложить свой код сюда если нужно..
Открытый код - это всегда хорошо. У группы есть раздел файлы. Туда
можно, например, размещать код. Если, с другой стороны, ваш проект будет
побольше, я бы рекомендовал для кода
vitaly333
vitaly333
> G. Kumfert and A. Pothen. Two improved algorithms for envelope and
> J. K. Reid and J. A. Scott. Ordering symmetric sparse matrices for small
> profile and wavefront. International Journal for Numerical Methods in
> Engineering, 45:1737-1755, 1999.http://epubs.cclrc.ac.uk/bitstream/128/raltr-1998016.pdf
улучшенный алгоритм Слоана. Только я никах не могу понять как
вычисляеться там size(i). Что это вообще такое?
Там написано что для вычисления incr(i) = cdeg(i) + size(i); - где
cdeg(i) - текущая степень вершины i, а вот про size(i) написано что
это вес мульти -вершины i. Если вам не трудно, Евгений, не могли бы
помочь мне разобраться как вычисляеться этот size(i). Тогда бы я смог
запрограммировать модернизированный алгоритм. Про это написано в 1-ой
статье на 10 стр.
Evgenii Rudnyi
Какие-то проблемы с кодировкой. Попробуйте, послать записку еще раз.
vitaly333
> Какие-то проблемы с кодировкой. Попробуйте, послать записку еще раз.
улучшенный алгоритм Слоана. Хотел было его реализовать да не могу
разобраться как там считаеться для каждой вершины графа такой
параметр:
incr(i) = cdeg(i) + size(i) ; - в статье написано что cdeg - это
текущая степень аершины i. С этим всё понятно. А вот про size(i)
написано что это вес мульти -вершины и всё. Как он высчитываеться ума
не приложу. Евгений , очень вас прошу, не могли бы вы посмотреть в
этой первой статье (стр. 10) про это. Может вы поймете. Обычный
алгоритм Слоана я уже реализовал. Хотелось бы также реализовать
улучшенную версию и сравнить с обычной.
Evgenii Rudnyi
Проще всего спросить авторов напрямую
http://www.cs.odu.edu/~pothen/software.html
Там даже есть ссылки на код, но они не живые. Сами странички, на которые
они ссылаются можно найти с помощью WaybackMachine
http://web.archive.org/collections/web.html
Например,
http://web.archive.org/web/20041010221057/www.cs.odu.edu/~kumfert/research/fastSloan/index.html
но самого кода мне найти не удалось. К слову сказать очень симпатичное фото
http://web.archive.org/web/20040930195357/http://www.cs.odu.edu/~kumfert/
А вот его новая страничка
vitaly333
> но самого кода мне найти не удалось.
такое size(i).
> Проще всего спросить авторов напрямую.
Я бы спросил. Но мои ужастные лигвистические способности в англ. языке
не позволяют мне это зделать.:(((
Evgenii Rudnyi
> не позволяют мне это зделать.:(((
Я послал вам примерный текст письма. А английский надо учить. Без него
никуда.
К слову сказать, в статье написано
We denote by size(i) the integer weight of a multi-vertex i
Это не означает, что size(i) - это просто число соединений ноды i?
vitaly333
> Я послал вам примерный текст письма. А английский надо учить. Без него
> никуда.
> К слову сказать, в статье написано
>
> We denote by size(i) the integer weight of a multi-vertex i
>
> Это не означает, что size(i) - это просто число соединений ноды i?
(degree(i));
Если бы size(i) - было число соединений узла i , то получаеться что
size(i) = degree(i). И формула incr(i) = cdeg(i) + size(i) выгляделы
бы не так а вот как incr(i) = 2*cdeg(i); Тогда бы просто не вводили
бы переменную size(i) так ведь? Но они вводят. Это означает что
degree(i) и size(i) совсем разные вещи.