Comments 62
Очень бы хотелось увидеть сравнение еще и с GMRES.
Вы имеете в виду реализацию GMRES в Матлабе?
Или в каком-то другом продукте?
Или в каком-то другом продукте?
Да где угодно, хоть в Python/scipy. Вот тут есть пример решения аж нелинейного интегро-дифференциального уравнения методом Крылова-Ньютона, где внутри именно что LGMRES. Оно решается при числе переменных 200x200 = 40000 на моем ультрабуке (i7-4500U) за 7 секунд. При размере сетки 400x400 = 160000 неизвестных, время решения 105 сек при включенной нелинейности и 80 сек при выключенной. И это при отсутствии прекондиционера.
Естественно, что нужно сравнивать на одних и тех же уравнениях и одном и том же компьютере…
Естественно, что нужно сравнивать на одних и тех же уравнениях и одном и том же компьютере…
Матан на Хабре в блоге 1С! Очень здорово, хотим еще!
Какие версии superLU и LAPACK были в тесте? И какие конкретно алгоритмы решения СЛАУ в них были использованы?
superLU — v.5.1
lapack — v.3.8.0, использовался SGESV/SGESVX, потому что решались матрицы в общем виде (не обязательно симметричные и положительно определённые).
Библиотека использует алгоритм факторизации.
lapack — v.3.8.0, использовался SGESV/SGESVX, потому что решались матрицы в общем виде (не обязательно симметричные и положительно определённые).
Библиотека использует алгоритм факторизации.
А у вас задача решить СЛАУ или найти LU факторизацию? Правда ли, что указанные солверы (supeLU, SGESV/SGESVX) делают LU факторизацию.
Вообще разреженные СЛАУ исследуют довольно давно, как минимум нужно иметь в виду упомянутые ранее в комментариях методы Крылова — для них базовая оценки не O(n^3), а O(nm), где m — количество ненулевых элементов (достигается кстати как раз в том числе за счет «списков смежности»). Уверен, Вы смогли бы ускориться за счет использования какой-нибудь разновидности метода Крылова после указанных графовых оптимизаций вместо Гаусса.
Пока что создается ощущение, что вы сравниваете «Гаусса» и «Гаусса + графовые оптимизации», и это ожидаемо, что в таком сравнении незаточенный под разреженность Гаусс будет медленней.
Откуда эта асимптотика была взята?
Вообще разреженные СЛАУ исследуют довольно давно, как минимум нужно иметь в виду упомянутые ранее в комментариях методы Крылова — для них базовая оценки не O(n^3), а O(nm), где m — количество ненулевых элементов (достигается кстати как раз в том числе за счет «списков смежности»). Уверен, Вы смогли бы ускориться за счет использования какой-нибудь разновидности метода Крылова после указанных графовых оптимизаций вместо Гаусса.
Пока что создается ощущение, что вы сравниваете «Гаусса» и «Гаусса + графовые оптимизации», и это ожидаемо, что в таком сравнении незаточенный под разреженность Гаусс будет медленней.
и в среднем и в лучшем случаях демонстрирует асимптотику Θ(n⋅log(n)⋅log(n))
Откуда эта асимптотика была взята?
1) Указанные солверы решают СЛАУ методом LU-факторизации (в частности superLU, lapack немного иначе раскладывает)
2)После графовых оптимизаций мы получаем плотные структуры, в которых применение метода Крылова не даст существенного выигрыша в асимптотике. Применение метода Крылова к исходному графу дало бы, как вы уже сказали, асимптотику в Θ(nm), что, конечно, проигрывает нашей в общем случае
3) Вывод этой асимптотики — хорошая тема для отдельной большой статьи, но если вкратце — из произведения глубины орграфа, среднего количества рёбер, смежных с вершиной и n.
2)После графовых оптимизаций мы получаем плотные структуры, в которых применение метода Крылова не даст существенного выигрыша в асимптотике. Применение метода Крылова к исходному графу дало бы, как вы уже сказали, асимптотику в Θ(nm), что, конечно, проигрывает нашей в общем случае
3) Вывод этой асимптотики — хорошая тема для отдельной большой статьи, но если вкратце — из произведения глубины орграфа, среднего количества рёбер, смежных с вершиной и n.
Интересно, вы пишите, что:
Далее, я не понимаю, как оценка Θ(nm) (где m — некоторая константа) может оказаться хуже, чем Θ(n⋅log(n)⋅log(n))?
Вывод этой асимптотики —… — из произведения глубины орграфа, среднего количества рёбер, смежных с вершиной и n.но в формуле я не вижу ни «глубины орграфа», ни «среднего количества рёбер, смежных с вершиной».
Далее, я не понимаю, как оценка Θ(nm) (где m — некоторая константа) может оказаться хуже, чем Θ(n⋅log(n)⋅log(n))?
m — не константа. А, вполне возможно, большое число. При коэффициенте заполнения 10% m=0.1*n^2
log(n) — средняя глубина орграфа при определенных допущениях. Так же log(n) — среднее число вершин, смежных с данной, при определенной структуре графа. Отсюда и оценка n*log(n)*log(n)
log(n) — средняя глубина орграфа при определенных допущениях. Так же log(n) — среднее число вершин, смежных с данной, при определенной структуре графа. Отсюда и оценка n*log(n)*log(n)
А почему среднее число вершин, смежных с данной — log(n)? У вас всего ребер ~ 0.1 * n^2, то средняя степень должна быть 2 * 0.1 * n.
Кроме того, Θ(n⋅log(n)⋅log(n)) асимптотически меньше, чем n^2, а у вас количество ненулевых коэффициентов ~0.1 * n^2, получается, что Ваш алгоритм делает меньше операций, чем размер выходных данных.
Кроме того, Θ(n⋅log(n)⋅log(n)) асимптотически меньше, чем n^2, а у вас количество ненулевых коэффициентов ~0.1 * n^2, получается, что Ваш алгоритм делает меньше операций, чем размер выходных данных.
Вот здесь есть результаты тестирования superLU, очень похожие на те, что мы получили.
Вы бы для начала научились релизы без багов выпускать, а потом уже слау решали.
такое впечатление, что в 1с понятие тестирование продукта отсутствует полностью.
такое впечатление, что в 1с понятие тестирование продукта отсутствует полностью.
Ну, справедливости ради, если сравнивать десктопную платформу с мобильной, а также с другими продуктами разных вендоров — количество багов вполне приемлимое.
Только не надо смешивать в кучу платформу 1С: Предприятие и конкретные решения на этой платформе. У самой платформы все довольно-таки не плохо. Об этом даже предыдущая статья в их блоге была.
UFO just landed and posted this here
Хорошо будем о платформе 8.3 от рождения как была глухой так и осталась. Когда пользователь пытается от крыть любой справочник, платформа постоянно переспрашивает вам точно открыть справочник? Такое ощущение что ты общаешься с глухим он тебя плохо слышит и постоянно уточняет или разработчики явно издеваются над пользователем.
или разработчики явно издеваются над пользователемЯ правильно Вас понял, что вы о работе в конфигурации в режиме пользователя? Если да, то о какой конфигурации идет речь? Только что ради любопытства открыл справочник контрагенты в БП (3.0.64.42), в рознице ((2.2.6.30, старенькая, но что нашлось на скорую руку) открыл «Склады» и «Номенклатура», ЗуП (3.1.6.6) — Сотрудники. Список я думаю можно продолжить, но уже результат — ни одного вопроса.
Второе:
от крыть любой справочник, платформа постоянно переспрашиваетНе платформа, а конфигурация. Отсюда вопрос — Вы о какой конфигурации говорите? Можете указать Платформу, Конфигурацию и ее релиз? Конфигурация типовая или «дописанная»?
В целом, могу помочь разобраться «почему», но в этом ли была цель Вашего сообщения?
В общем случае ваше утверждение абсолютно некорректно (мягко говоря).
Это проверяется примитивной конфигурацией, которую вы можете создать примерно за 30 секунд.
Хочется провозгласить стандартный лозунг — пруфы в студию!
В том смысле, что для начала хочется услышать полный номер версии платформы (включая разрядность), полное наименование используемой конфигурации (название, полный номер) и используемую ОС.
Это проверяется примитивной конфигурацией, которую вы можете создать примерно за 30 секунд.
Хочется провозгласить стандартный лозунг — пруфы в студию!
В том смысле, что для начала хочется услышать полный номер версии платформы (включая разрядность), полное наименование используемой конфигурации (название, полный номер) и используемую ОС.
Платформа 8.3, управляемая форма на любой типовой конфигурации. К примеру создайте новый документ продажи или покупки попробуйте выбрать контрагента. По нажатию кнопки открыть форму выбора контрагента вам сначала откроется диалог выбора вариантов действий
Вот собственно этот диалог и есть издевательство на пользователем. Зачем переспрашивать пользователя если он конкретно нажал кнопку Показать все?
И это не только на выборе контрагентов.
Последние набранные
Введите строку поиска
Нажмите Показать все для выбора
Нажмите + (создать) для добавления
Вот собственно этот диалог и есть издевательство на пользователем. Зачем переспрашивать пользователя если он конкретно нажал кнопку Показать все?
И это не только на выборе контрагентов.
Берем УТ 11.4.3. Открываем «Заказ клиента». Смотрим…
1. Поле «Контрагент» — в нем нет кнопки открытия формы выбора. А есть поле ввода (которое уже давно рекомендуется для ввода(!) имени) и есть кнопка «Выбрать из списка» (на ней треугольничек нарисован), по нажатию на которую открывается история ввода, где расположены 10 последних выборов оператора и возможность открыть форму выбора. При этом, если в поле «Контрагент» нажать кнопку F4 — сразу откроется форма выбора контрагента (но и история выбора останется доступной).
2. Справа от поля «Контрагент» находится поле «Склад». И вот там кнопка открытия формы выбора (на ней нарисовано ...) есть сразу. И ее нажатие открывает сразу форму выбора, без отображения истории ввода.
И это везде.
Платформа, в принципе, старается обеспечить максимально эффективную работу с документами/справочниками без использования мыши, только с клавиатуры. Практика показала, что подбор списка выбора при вводе текста — значительно эффективнее, чем копание в списках из тысяч и десятков тысяч элементов произвольной глубины вложенности.
Похоже, что вы не очень хотите изучать то, с чем приходится работать. Это печально :(
1. Поле «Контрагент» — в нем нет кнопки открытия формы выбора. А есть поле ввода (которое уже давно рекомендуется для ввода(!) имени) и есть кнопка «Выбрать из списка» (на ней треугольничек нарисован), по нажатию на которую открывается история ввода, где расположены 10 последних выборов оператора и возможность открыть форму выбора. При этом, если в поле «Контрагент» нажать кнопку F4 — сразу откроется форма выбора контрагента (но и история выбора останется доступной).
2. Справа от поля «Контрагент» находится поле «Склад». И вот там кнопка открытия формы выбора (на ней нарисовано ...) есть сразу. И ее нажатие открывает сразу форму выбора, без отображения истории ввода.
И это везде.
Платформа, в принципе, старается обеспечить максимально эффективную работу с документами/справочниками без использования мыши, только с клавиатуры. Практика показала, что подбор списка выбора при вводе текста — значительно эффективнее, чем копание в списках из тысяч и десятков тысяч элементов произвольной глубины вложенности.
Похоже, что вы не очень хотите изучать то, с чем приходится работать. Это печально :(
Платформа, в принципе, старается обеспечить максимально эффективную работу с документами/справочниками без использования мыши, только с клавиатуры.
Эффективность данного предложения очень сомнительная скорее отрицательная.
Двойной или тройной стук мышкой (даже если и клавиатурой сначала Tab потом F4) по одному реквизиту это уже не эффективно.
Новый документ — новая жизнь! Для чего эта история выпадающего списка из 10 последних? Из 100 новых документов максимум в 5 повторится контрагент причем в остальных 95 случаях в два раза больше придется выбирать нового контрагента, извините но это трата человеческого времени а не машины. Да и не каждый пользователь способен в голове держать массу команд от 1С.
Следующие пробуйте постоянно набирать тысячи разных позиций примерного наименования
ВНА-ПА-П-10/630-||-20зп УХЛ2
ПП53-16-1-149-1-УХЛ2
ПП53-25-1-045-1-УХЛ3
ОСК 10-20-Е05-3 УХЛ1
РЕ 19-45-31120 00 УХЛ3
Извините но у нас в стране не все только водкой и лицензиями для 1с торгуют.
Если пользователь попал мышкой с первого раза в треугольник, должен открыться справочник для выбора, а не пожелания от 1С.
Эффективность данного предложения очень сомнительная скорее отрицательная.
Проф.операторы слышат такое утверждение с удивлением.
Для выбора нового контрагента стоит начать набирать его название. Ведь его выбирают не случайным числом, а потому, что он где указан (назван по телефону, в письме указан и т.д.)
если и клавиатурой сначала Tab потом F4
Для работы в нормально созданной форме, как правило, нужны следующие кнопки: ENTER, F4 и курсорные стрелки. Мышь нужна для выбора закладок и еще в ряде особых случаев. ENTER — великолепно обходит элементы.
Да и не каждый пользователь способен в голове держать массу команд от 1С.
Команд, которые необходимы каждый день — очень небольшой. И чтобы не запоминать — есть справка. А еще есть обучение использованию системой, где рассказывают, как пользоваться системой эффективно.
По вашему набору наименований достаточно набирать хотя-бы стартовые наименования компонентов, чтобы получать сокращенный перечень. При этом нет необходимости набирать все наименование — список адаптируется к набору. Т.е. набрав «пп53» я получу список из все переключателей, а набрав «пп53-16» — ограничу этот список переключателями на 16А. При этом можно указать, что в справочнике номенклатуры поиск при вводе будет идти не по началу строки (поведение по умолчанию), а по любому вхождению.
Также стоит помнить, что человек, долго занимающийся «своей» областью хорошо представляет себе правила формирования наименований и что они означают. Поэтому для такого человека преобразование фразы во фрагмент наименования происходит очень быстро.
Несмотря на все вышесказанное, я вполне допускаю, что предложенное поведение в используемом прикладном решении вас не устраивает. Ну так исправьте его! Для этого надо для нужных полей в документе(-ах) сделать «пару» кликов мышью и включить кнопку выбора вместо кнопки истории (а можно оставить и то и то).
Извините но у нас в стране не все только водкой и лицензиями для 1с торгуют.
Не может быть!
ЗЫ: Осталось только понять, как наша дискуссия относится к теме поста :)
Затем, что это не кнопка «Показать все», а кнопка «Выбрать из списка», о чем свидетельствует иконка и контекстная подсказка. Кнопка выбора выглядит иначе: screenpresso.com/=qtSDc Также, если хочется открыть форму выбора сразу, можно нажать «F4» или правой кнопкой — «Выбрать». Лично мне и нашим пользователям такой подход, кажется логичным. Но ведь всем угодить невозможно, верно? :)
Слова не специалиста, а обиженного пользователя.
(от куда вы вообще узнали такие умные слова как «платформе 8.3»?)
На практике в режиме конфигуратора для справочников выставляются настройки — «нужен ли список последних указанных в поле ввода элементов?», «можно ли разрешить создание новых элементов при вводе?». Далее разработчик прикладного решения сам решает какое поведение системы будет более удобным для пользователей его продукта.
Я поддерживаю старые конфигурации на обычных формах и меня иногда просят реализовать подобные «списки историй» — потому что это удобно и экономит людям время.
(от куда вы вообще узнали такие умные слова как «платформе 8.3»?)
На практике в режиме конфигуратора для справочников выставляются настройки — «нужен ли список последних указанных в поле ввода элементов?», «можно ли разрешить создание новых элементов при вводе?». Далее разработчик прикладного решения сам решает какое поведение системы будет более удобным для пользователей его продукта.
Эффективность данного предложения очень сомнительная скорее отрицательная.
Двойной или тройной стук мышкой (даже если и клавиатурой сначала Tab потом F4) по одному реквизиту это уже не эффективно.
Новый документ — новая жизнь! Для чего эта история выпадающего списка из 10 последних?
Я поддерживаю старые конфигурации на обычных формах и меня иногда просят реализовать подобные «списки историй» — потому что это удобно и экономит людям время.
Приведенные выше графики были получены при решении систем на одном ядре? Если да, то как ваш алгоритм масшатбируется на большее число ядер? Я идеале, конечно, хотелось бы проверить полученные результаты (хотя код вы, наверно, в открытый доступ не выложите), а то как-то с трудом верится что ваша реализация работает намного быстрее superLU.
Приведенные выше графики были получены при решении систем на одном ядре?
Да, на одном.
Если да, то как ваш алгоритм масштабируется на большее число ядер?
В механизме предусмотрена возможность распараллеливания. Причём возможно как параллельное решение нескольких систем уравнений, так и распараллеливание решения каждой из систем. Использование вычислительных ресурсов можно настроить специальным свойством.
Даже для одного ядра ускорение по сравнению с superLU впечатляет (хотя, если честно, с трудом верится что это так на самом деле). Еще неплохо было бы сравнить с сольвером MUMPS. А вы можете привести графики ускорения расчета для нескольких ядер?
Графики в многопоточном режиме сейчас, к сожалению, сделать не сможем — это займет существенное время. К тому же сравнивать многопоточный режим для нашего механизма и сторонних библиотек может быть не вполне корректно, т.к. библиотеки могут работать с потоками по другому алгоритму, чем наш механизм.
Постараемся к релизу нашего механизма предоставить более полную информацию по быстродействию в многопоточном варианте.
Постараемся к релизу нашего механизма предоставить более полную информацию по быстродействию в многопоточном варианте.
А где опубликован оригинал метода?
К рисунку под фразой «Граф принимает следующий вид:»
А куда же делась вершина 0?
А куда же делась вершина 0?
Вершина была редуцирована. Об этом говорится в посте, и приведённый рисунок как раз иллюстрирует это.
я извиняюсь, может я туплю, но как могла редуцироваться переменная x0, если редуцировались только x3, x1 и x2 к этому моменту? А x0 вообще равно 28 и про это ни слова.
как могла редуцироваться переменная x0
Цитата из статьи:
Аналогично поступим с уравнением 0, так как в него входит всего одна переменная
Так это написано про связь A[1][0], но связь A[0][1] то останется. Куда она делась?
По мне так ее нужно нарисовать стрелочкой от 0 к 1.
По мне так ее нужно нарисовать стрелочкой от 0 к 1.
так это не переменная x0 а уравнение 0, в которое входит одна переменная x1 она и редуцировалась!
ок, а как же переменная x0 в уравнении 1? куда делась она? на рисунке ее нет
я тоже задаюсь этим вопросом ))) так как переменная x0 редуцироваться не может, это очевидно. Поэтому обратилась к PeterG в комментариях. Видимо где-то потеря произошла у автора )
ну да, там не сложно поправить, главное идея понятна
Переменная не редуцируется. Редуцировалось уравнение 0. Вершину с картинки убрали для явного понимания. Вообще должно исчезнуть одно ребро. Постараемся сделать картинку для иллюстрации.
нет!
вообще давайте забудем про слово «редуцируется», оно как-то уводит нас от смысла. А смысл в том что как раз должно остаться ребро к 0. А ребро от 0 должно исчезнуть. Вот и все.
вообще давайте забудем про слово «редуцируется», оно как-то уводит нас от смысла. А смысл в том что как раз должно остаться ребро к 0. А ребро от 0 должно исчезнуть. Вот и все.
Да, вы правы, удаление нулевой вершины — это следующий шаг, который был некорректно внесён на иллюстрацию. Схема должна выглядеть так(картинка прикреплена). Подразумевалось, что, зная значение х1, мы подставим его во все уравнения (таких у нас три, судя по рёбрам), и х0 сразу станет разрешим, тогда как для нахождения х2 и х4 потребуется ещё один шаг редукции.
Спасибо за внимательность.
Спасибо за внимательность.
В статье говорится что «шаг алгоритма стоит повторять до тех пор, пока возможно редуцирование хотя бы одной из вершин»
Поэтому вопрос — какова оценка сложности алгоритма с учетом этого цикла? Возможно ли что итеративное редуцирование приведет к долгой работе алгоритма?
Проблема в том что после того как мы редуцировали переменную мы подставляем ее в другие уравнения чтобы опять же редуцировать другие переменные. Насколько дешево это будет?
Поэтому вопрос — какова оценка сложности алгоритма с учетом этого цикла? Возможно ли что итеративное редуцирование приведет к долгой работе алгоритма?
Проблема в том что после того как мы редуцировали переменную мы подставляем ее в другие уравнения чтобы опять же редуцировать другие переменные. Насколько дешево это будет?
Скажите, пожалуйста, сравнивали ли Вы эффективность метода с pardiso?
Могут ли применяться подобные идеи для решения (в смысле метода наименьших квадратов) переопределенных заведомо несовместных разреженных СЛАУ?
Могут ли применяться подобные идеи для решения (в смысле метода наименьших квадратов) переопределенных заведомо несовместных разреженных СЛАУ?
Del
Круто!
Вспомнил, как 10 лет назад из-за медленной работы 1с с числами, пришлось написать на коленке внешнюю компоненту на С++ с решением системы уравнений методом Гаусса. И расчет с нескольких часов ускорился до нескольких десятков секунд, а я приобрел немалый авторитет в глазах коллег :)
Вспомнил, как 10 лет назад из-за медленной работы 1с с числами, пришлось написать на коленке внешнюю компоненту на С++ с решением системы уравнений методом Гаусса. И расчет с нескольких часов ускорился до нескольких десятков секунд, а я приобрел немалый авторитет в глазах коллег :)
Если матрица коэффициентов A[i][j] вырожденная (нулевой детерминант), то что выдается в качестве ответа? Ну или более общий вопрос,- можно ли оценить значение детерминанта матрицы при помощи описанного функционала?
Если матрица вырождена — выдаётся ответ для невырожденной подматрицы, а несколько ответов (по переменным, удаление которых приводит к линейно-независимой
системе) принимаются равными нулю.
Оценить значение определителя можно из формулы Крамера (используя описанную выше функциональность), но намного эффективнее будет использовать алгоритм поиска компонент сильной связности в графе, найти определитель для всех подматриц, соответствующих компонентам (это намного быстрее, можно использовать стандартный кубический алгоритм) и, перемножив их, получить определитель с точностью до умножения на -1.
системе) принимаются равными нулю.
Оценить значение определителя можно из формулы Крамера (используя описанную выше функциональность), но намного эффективнее будет использовать алгоритм поиска компонент сильной связности в графе, найти определитель для всех подматриц, соответствующих компонентам (это намного быстрее, можно использовать стандартный кубический алгоритм) и, перемножив их, получить определитель с точностью до умножения на -1.
Спасибо за ответ. Можно-то все сделать, понятно. Сейчас все, кому приспичило, как-то выкручиваются.
Но не разумнее ли было встроить базовый функционал линейной алгебры сразу, а не нарезать по кусочкам, решая хоть и важную, но все-таки частную задачу типа расчета себестоимости? Обращение матрицы и вычисление детерминанта — куда уж базовей вроде бы. Тем более почти все есть для этого.
Правда, определение собственных значений и векторов матрицы, тоже к базовым можно отнести.
Базы 1С давно уже накопили большое количество данных. Надо расширять встроенные средства их анализа.
Но не разумнее ли было встроить базовый функционал линейной алгебры сразу, а не нарезать по кусочкам, решая хоть и важную, но все-таки частную задачу типа расчета себестоимости? Обращение матрицы и вычисление детерминанта — куда уж базовей вроде бы. Тем более почти все есть для этого.
Правда, определение собственных значений и векторов матрицы, тоже к базовым можно отнести.
Базы 1С давно уже накопили большое количество данных. Надо расширять встроенные средства их анализа.
Sign up to leave a comment.
Как мы в «1С: Предприятии» решаем системы алгебраических уравнений