Приостановка расчета

[Гость ISPA]

Математика не занимается искусством, по крайнем мере взрослая.

Так Федор вам ли мне объяснять, что под термином искусство нужно понимать “искусство”. Зайду на второй круг, третьего уже будет. Взрослые, серьезные МКЭ комплексы не будут заниматься неполным разложением Холецкого. Полное разложением Холецкого всегда можно получить для КЭ матрицы. Взрослый комплекс знает как это сделать. Что касается неполного разложения, то не получится привести матрицу к треугольному виду любым методом. Тут дело не в методе, а в “неполноценности” разложения. Вроде не забыл в нужном месте поставить кавычки. Суть то вы в любом случае уже уловили.

[Fedor 1 597]

Я знаю, что такое программа, а таинстенные комплексы это туманные выдумки типа тайного знания браминов. Мне голову не морочьте. Форд говаривал - если вместо прямых и ясных ответов начинают говорить об искусстве анализа - значит хотят надуть

" Полное разложением Холецкого всегда можно получить для КЭ матрицы" - само-собой в поле комплексных чисел, матрицы мкэ полуопределенные, а за счет ошибок округления бывают и слегка неположительно определенные

[Гость ISPA]

Форд говаривал - если вместо прямых и ясных ответов начинают говорить об искусстве анализа - значит хотят надуть

Не передергивайте Федор. Прием известный. Я даю прямой и ясный ответ, что

неполное разложение Холецкого не совсем подходит для МКЭ в качестве предобуславливателя. А еще короче совсем не подходит. И объяснил почему.

Просто теоретические изыскания умных дядей (я говорю про статьи в Интернете) не всегда соответствуют расчетной практике.

[Fedor 1 597]

Подходит все, что позволяет вычислить произведение вектора на обратную матрицу, матрицы похожей в каком -нибудь смысле на исходную. Никто алгебру под какой-то прикладной метод переписывать не будет. Кесарю - кесарево, а слесарю - слесарево :)

[EsDur 0]

Я занимаюсь итерационными методами уже более 20 лет, практик. Являюсь разработчиком одного из серъезных программных комплексов по решению инженерных задач, отвечаю в том числе за алгоритмы решения систем уравнений. Имею кучу статей по алгоритмам, скоро дисертацию буду защищать по этой тематике. Сейчас в том числе работаю на суперкомпьютере Ломоносов, доступ к которому пока мало у кого есть.

Хотелось бы уточнить немного. Тут многое наговорили, не буду уточнять кто. Многочисленные неграмотные и безапелляционные заявления. Постараюсь корректно и по делу, без эмоций и флуда.

По поводу разложения Холесского. Для больших задач применять прямые методы - безумие. Тот кто агитирует так делать, просто не осознает что такое прямое разложение в случае 3D задачи, никаких ресурсов не хватит, даже суперкомпьютера Ломоносов. Для задач МКЭ можно до какого-то момента делать прямое разложение, а дальше - нет. Мы например сейчас уже решаем задачи до 100-300 млн. Итерационными методами. Для МКЭ в том числе. По договорам с некоторыми серъезными организациями скоро будем решать до 5 млрд. По поводу неполноценности неполного разложения. Существуют математические подходы и алгоритмы, которые в SPD случае гарантируют существование и устойчивость неполного разложения (могу привести формулировки теорем и доказательства, или ссылки на работы). Существуют итерационные алгоритмы, которые в случае даже вырожденных задач с согласованной правой частью способны вычислить нормальное псевдорешение, могу привести алгоритмы, теоремы и доказательства.

Господа, неплохо бы некоторым сначала разобраться в тематике, а только потом допускать безапелляционные высказывания.

[Fedor 1 597]

"Тот кто агитирует так делать, просто не осознает что такое прямое разложение в случае 3D задачи" - до миллиона и Ansys обычно выбирает прямое разложение. Домики 20-30 этадные с кучей земли молотит за 5-10 минут на обычном компьютере с приемлимой для проектирования точностью. Есть же книжки Дрорджа и Лю, Писсанецки и другие по разреженным технологиям.

Сказать то что хотели чисто конкретно ?

Доказывайте, что неправильно, ярлыки мы вешать умеем лучше Вас можете поверить

[EsDur 0]

"Тот кто агитирует так делать, просто не осознает что такое прямое разложение в случае 3D задачи" - до миллиона и Ansys обычно выбирает прямое разложение. Домики 20-30 этадные с кучей земли молотит за 5-10 минут на обычном компьютере с приемлимой для проектирования точностью. Есть же книжки Дрорджа и Лю, Писсанецки и другие по разреженным технологиям.

Сказать то что хотели чисто конкретно ?

Доказывайте, что неправильно, ярлыки мы вешать умеем лучше Вас можете поверить

Попробую доказать. Для прямых методов проблема с окаймлением (ND упорядочивание) либо с шириной ленты (упорядочивание типа обратного катхилл макки), зависит от выбора типа оптимального упорядочивания. Для 3D задачи с непустым объемом окаймление или ширина ленты порождается объемом и порядка поверхности. Задачи о которых вы говорите - квази одномерные, у них почти линейные связи. Когда в каждой квази линии будет порядка 100x100 ячеек в каждом слое ячеек - вот тогда это будет реальная 3D задача. Для нее ширина ленты или окаймления - это ~поверхность, что есть размерность в степени 2/3. Для 100 млн. получается около миллиона. Плотные вычисления с такими по порядку величины матрицами - флаг в руки. Не хватит ни памяти ни вычислений. Ваш пример, повторюсь не проходит, задача квази одномерна. Для них согласен можно использовать прямые методы.

[Fedor 1 597]

" квази одномерна" - мне нравится Ваш квази подход, спасибо

В жизни редко встречаются сильно связанные задачки вроде кубика, можно же и к стреловидным сводить и так далее. В силу морфизма матриц размерность не так уж и важна для изучения свойств. Понятно, что у подобных в смысле заполнения матриц и свойства будут примерно подобными.

Обычно в разреженных число умножений порядка n n log n насколько помню. Так что вопрос времени и памяти. Просто раньше много экспериментировали на всяких итерационных методах и в итоге они почти всегда проирывали прямым на матрицах до миллиона .

Ваше утверждение говорит, что эффективность метода зависит от масштаба, а в общем случае это противоречит морфизмам матричным, если конечно речь идет об эквивалентной точности решения, а если еще много правых частей, то уж и вовсе сомнительным.

[EsDur 0]

" квази одномерна" - мне нравится Ваш квази подход, спасибо

В жизни редко встречаются сильно связанные задачки вроде кубика, можно же и к стреловидным сводить и так далее. В силу морфизма матриц размерность не так уж и важна для изучения свойств. Понятно, что у подобных в смысле заполнения матриц и свойства будут примерно подобными.

Обычно в разреженных число умножений порядка n n log n насколько помню. Так что вопрос времени и памяти. Просто раньше много экспериментировали на всяких итерационных методах и в итоге они почти всегда проирывали прямым на матрицах до миллиона .

Ваше утверждение говорит, что эффективность метода зависит от масштаба, а в общем случае это противоречит морфизмам матричным, если конечно речь идет об эквивалентной точности решения, а если еще много правых частей, то уж и вовсе сомнительным.

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

Теперь что касается объема и стреловидности. Для тех же задач механики с линейными структурами типа стержней разной формы можно конечно до некоторого момента сетку строить в основном продольную, если нас интересуют в основном продольные возмущения в конструкции. Однако есть куча серъезных задач, в которых важны все аспекты поведения конструкции, и с высокой точностью. В том числе и из-за возможных резонанстных явлений. В таких конструкциях уже нужно разрешение по всем направлениям. Я уже не говорю про задачи типа гидродинамики, где вообще основное - 3D объем, и интересует объемное турбулентное течение жидкости. А тепловые задачи? Те же задачи охлаждения критичны для работы современных компьютеров. А там и механика, и гидродинамика, и тепло. В объеме.

Про морфизмы можно поподробнее?

[EsDur 0]

" квази одномерна" - мне нравится Ваш квази подход, спасибо

В жизни редко встречаются сильно связанные задачки вроде кубика, можно же и к стреловидным сводить и так далее. В силу морфизма матриц размерность не так уж и важна для изучения свойств. Понятно, что у подобных в смысле заполнения матриц и свойства будут примерно подобными.

Обычно в разреженных число умножений порядка n n log n насколько помню. Так что вопрос времени и памяти. Просто раньше много экспериментировали на всяких итерационных методах и в итоге они почти всегда проирывали прямым на матрицах до миллиона .

Ваше утверждение говорит, что эффективность метода зависит от масштаба, а в общем случае это противоречит морфизмам матричным, если конечно речь идет об эквивалентной точности решения, а если еще много правых частей, то уж и вовсе сомнительным.

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

Теперь что касается объема и стреловидности. Для тех же задач механики с линейными структурами типа стержней разной формы можно конечно до некоторого момента сетку строить в основном продольную, если нас интересуют в основном продольные возмущения в конструкции. Однако есть куча серъезных задач, в которых важны все аспекты поведения конструкции, и с высокой точностью. В том числе и из-за возможных резонанстных явлений. В таких конструкциях уже нужно разрешение по всем направлениям. Я уже не говорю про задачи типа гидродинамики, где вообще основное - 3D объем, и интересует объемное турбулентное течение жидкости. А тепловые задачи? Те же задачи охлаждения критичны для работы современных компьютеров. А там и механика, и гидродинамика, и тепло. В объеме.

Про морфизмы можно поподробнее?

[Гость ISPA]

... там для первой правой части - около 500 итераций, для второй - около 100 итераций, для третьей и последующих - около 30.

А вот это действительно интересно и актуально. Дайте пару ссылок для более подробного ознакомления или здесь объясните принцип.

[EsDur 0]

А вот это действительно интересно и актуально. Дайте пару ссылок для более подробного ознакомления или здесь объясните принцип.

Могу рассказать принцип и дать ссылку на базовую предыдущую статью.

Принцип в том, что текущая скорость сходимости алгоритмов Крыловского типа определяется так называемым монотонной характеристикой подпространства - обобщенным обратным числом обусловленности на подпространстве (Харченко С.А., Еремин А.Ю., “Новые алгоритмы типа GMRES(k) с рестартами и анализ их свойств сходимости на основе QR формы матричных соотношений“, Зап. Научн. Семин. ПОМИ, т. 268, 2000, 190-241.). Значение этой характиристики в общем несимметричном незнакоопределенном случае всегда лежит в пределах [0,1], и чем ближе она к 1, тем быстрее сходится алгоритм. Суперлинейная сходимость проявляется тогда, когда резко, скачком, меняется значение этой характеристики в сторону увеличения. Для первой правой части можно найти бо'льшую часть подпространства, нужного для хорошей сходимости (оно кстати как правило имеет размерность значительно меньшую чем число итераций). Затем это пространство используется как начальное для следующей правой части, и снова достраивается. Затем для следующей. При правильной реализации этого алгоритма (с ортогонализациями на основе преобразований Хаусхолдера) алгоритм чрезвычайно устойчив к ошибкам округления.

[Гость ISPA]

Спасибо. Я так понимаю, что смотреть надо здесь:

<noindex>http://www.mathnet.ru/php/archive.phtml?ws...option_lang=rus</noindex>

[Гость ISPA]

Скажите EsDur через какое количество итераций вы рекомендуете делать рестарт? Это позволит оценить накладные расходы на память для ортогонализации. И зависит ли это число от обусловленности матрицы в реальных задачах.

[Fedor 1 597]

"В линейной алгебре есть такой термин - проклятие размерности, вам он похоже неизвестен" - вообще-то их три в математике.

Трехдиагонализация, насколько знаю все-таки используется для поиска собственных чисел и векторов. Для решения систем это экзотика. В любом случае число потерянных цифр в решении - десятичный логарифм от числа обусловленности и от размерности не зависит. Кто-то из классиков, вроде фон Нейман доказал, что если ошибки округления будут вести себя наихудшим образом, то нет шансов решить даже систему из 100 уравнений, как и используя правило Крамера, однако природе случайна, а не злокознена

[EsDur 0]

Скажите EsDur через какое количество итераций вы рекомендуете делать рестарт? Это позволит оценить накладные расходы на память для ортогонализации. И зависит ли это число от обусловленности матрицы в реальных задачах.

Как ни странно, алгоритм прекрасно работает при очень малом размере цикла. Я использую 10. Если при этом после каждого такого цикла сохранять даже только одно наихудшее с точки зрения сходимости направление, и периодически делать двойные уже чисто спектральные фильтрации после нескольких рестартов (я делаю двойные после 10 циклов), то накладные расходы удивительно минимальны. Спектральные параметры фильтрации нужно брать соответствующие, например 3*10^-3 младшее и 2. - старшее. Например, после при 500 итераций суммарно требуется ~60 векторов. А сходимость - как будто рестартов нет вовсе, хотя их аж > 50. Конечно 60 векторов - это тоже немало если 7-ми точечный шаблон, но у нас шаблоны не маленькие и имеется немаленькое заполнение предобуславливания.

Кстати, я тут слышал что у Вас есть опыт по использованию граф. процессоров для подобного типа задач. Может поделитесь? Одно общее дело делаем, нужно догонять и обходить ANSYS, конкурировать надо с ним, а не между собой.

[a_schelyaev 366]

В гости приглашай...

[EsDur 0]

"В линейной алгебре есть такой термин - проклятие размерности, вам он похоже неизвестен" - вообще-то их три в математике.

Трехдиагонализация, насколько знаю все-таки используется для поиска собственных чисел и векторов. Для решения систем это экзотика. В любом случае число потерянных цифр в решении - десятичный логарифм от числа обусловленности и от размерности не зависит. Кто-то из классиков, вроде фон Нейман доказал, что если ошибки округления будут вести себя наихудшим образом, то нет шансов решить даже систему из 100 уравнений, как и используя правило Крамера, однако природе случайна, а не злокознена

Число потерянных цифр в решении не всегда есть десятичный логарифм от числа обусловленности. Это зависит от правой части и соотношения между нормой компонент в правой части по соответствующим сингулярным векторам и сингулярными числами матрицы. В частности, даже для вырожденной матрицы при хорошо согласованной правой части иногда можно получить все правильные цифры в решении.

Под проклятием размерности не обязательно имеется в виду мерность пространства - это и банальный рост числа неизвестных. В частности, увеличение размерности задач на порядок в линейной алгебре почти всегда приводило к кардинальному пересмотру всех алгоритмов. Можете проследить историю вопроса. Плюс к тому, есть множество задач где размерность - реально значительно больше чем 3. Во первых, никто не отменял возможности в лоб моделировать время как четвертое измерение, и такие подходы есть. В задачах моделирования динамики молекул насколько я знаю мерность простравнства значительно выше чем 3 - и там очень хитрые алгоритмы и подходы используются.

Трехдиагонализация - вещь хорошая, и действительно является первым шагом при решении спектральных задач, но в лоб ее использовать можно только для маленьких задач. Для частичных спектральных задач с большими разреженными матрицами сначала нужно правильно редуцировать задачу к задаче относительно маленькой размерности, а только затем использовать алгоритмы для плотных матриц с предварительной трехдиагонализацией.

[Гость ISPA]

Как ни странно, алгоритм прекрасно работает при очень малом размере цикла. Я использую 10.

Что же. Это очень и очень радует. Я в свое время много делал тестов с векторами Ланцоша, там эта идея не проходит.

Кстати, я тут слышал что у Вас есть опыт по использованию граф. процессоров для подобного типа задач. Может поделитесь? Одно общее дело делаем, нужно догонять и обходить ANSYS, конкурировать надо с ним, а не между собой.

Если вы поделитесь своими наработками, то я двумя руками за! Наверняка у вас есть хау-ноу. В России без этого не бывает. Кстати, опять вопрос. Рекомендуете ли вы попробовать ваш алгоритм на симметричных положительно определенных матрицах? Или может уже есть такой опыт.

А что касается ANSYS так он не силен в итерационных методах, поэтому и рекламирует прямой метод с минимальным заполнением матрицы. Тот же метод который разработали вы очень хорош будет в задачах потери устойчивости и собственных форм методом Ланцоша.

Что касается графических ускорителей, то с появлением на рынке TESLA S 2070 пусть ANSYS думает как ему догнать и перегнать российские разработки.

[EsDur 0]

Что же. Это очень и очень радует. Я в свое время много делал тестов с векторами Ланцоша, там эта идея не проходит.

Если вы поделитесь своими наработками, то я двумя руками за! Наверняка у вас есть хау-ноу. В России без этого не бывает. Кстати, опять вопрос. Рекомендуете ли вы попробовать ваш алгоритм на симметричных положительно определенных матрицах? Или может уже есть такой опыт.

А что касается ANSYS так он не силен в итерационных методах, поэтому и рекламирует прямой метод с минимальным заполнением матрицы. Тот же метод который разработали вы очень хорош будет в задачах потери устойчивости и собственных форм методом Ланцоша.

Что касается графических ускорителей, то с появлением на рынке TESLA S 2070 пусть ANSYS думает как ему догнать и перегнать российские разработки.

По поводу SPD матриц. Если сравнивать алгоритмы в одних и тех же условиях - одна правая часть и нет предыстории вычислений - то CG лучше, из-за дополнительных операций на ортогонализации и все-таки некоторого увеличения числа итераций (до 1.5 раз) по сравнению с алгоритмами без рестартов. Если правых частей много или есть предыстория вычисления с похожими матрицами - во тут и поконкурировать и значительно выиграть можно, буду скоро публиковать статью об этом. Более кардинальный эффект дает использование для SPD матриц высококачественных предобуславливаний.

По поводу возможного сотрудничества - приезжайте к нам, поговорим подробнее. Если у вас есть открытые материалы с результатами - хотелось бы предварительно ознакомиться, чтобы можно было вести предметное обсуждение. Ноу хау у нас конечно есть.