Comments 14
А как насчет критерия треугольника (не помню точно, как он сейчас называется) — не считать S(f,h) если уже подсчитаны S(f,g) и S(g,h) (при определенных условиях)? И потом… я понимаю, что поддерживать первую часть авторедуцированной не очень просто. Но почему бы не редуцировать полином, который мы берем из второй части, по первой — перед вычислением S-элементов? Это-то должно быть совсем легко.
И, кстати, проверяется ли при добавлении S-элемента во вторую часть, что его там еще не было? Если нет, то система должна расти очень быстро…
И, кстати, проверяется ли при добавлении S-элемента во вторую часть, что его там еще не было? Если нет, то система должна расти очень быстро…
Про критерий треугольника я не видел даже в книге Кокса, спасибо за информацию.
По поводу редукции перед вычислением s полиномов я наверное соглашусь, к тому же это позволит избавиться от повторений во второй части. Хотя я не до конца уверен что они там могут появиться.
По поводу редукции перед вычислением s полиномов я наверное соглашусь, к тому же это позволит избавиться от повторений во второй части. Хотя я не до конца уверен что они там могут появиться.
Критерий упоминается, например, на этой страничке:
www.scholarpedia.org/article/Buchberger%27s_algorithm#Deletion_Criteria
и называется Chain Criterion.
А насчет повторений — возьмите систему f0=x, f1=y, f2=x*y+z. (x>y>z). Когда начнёте добавлять f2 к базису {f0,f1}, получится S(f0,f2)=f2*1-f0*y=z, S(f1,f2)=f2*1-f1*x=z. В итоге, во вторую часть z добавится дважды. И потом (для более сложных систем) количество одинаковых многочленов начнет расти ещё быстрее.
www.scholarpedia.org/article/Buchberger%27s_algorithm#Deletion_Criteria
и называется Chain Criterion.
А насчет повторений — возьмите систему f0=x, f1=y, f2=x*y+z. (x>y>z). Когда начнёте добавлять f2 к базису {f0,f1}, получится S(f0,f2)=f2*1-f0*y=z, S(f1,f2)=f2*1-f1*x=z. В итоге, во вторую часть z добавится дважды. И потом (для более сложных систем) количество одинаковых многочленов начнет расти ещё быстрее.
Возможно, вы видели труд С. Мешвелиани с реализацией алгоритмов вычислительной алгебры на Хаскеле.
Автор, правда, впоследствии разочаровался в Хаскеле, из-за невозможности создания в рантайме типов вроде «факторпространство кольца полиномов K[x,y,z] по идеалу I»
Автор, правда, впоследствии разочаровался в Хаскеле, из-за невозможности создания в рантайме типов вроде «факторпространство кольца полиномов K[x,y,z] по идеалу I»
Понимаю, что этот вопрос к данному посту скорее оффтопик и виртуально пожимаю руку за самоотверженность, но все же вопрос задам: чем было продиктовано решение реализовывать вычисления самостоятельно и не пользоваться готовым (singular, macaulay2 etc)?
На всякий случай — я вполне понимаю аргумент «пробовали, было слишком медленно/памяти не хватило», самому приходилось идти нестандартными путями.
На всякий случай — я вполне понимаю аргумент «пробовали, было слишком медленно/памяти не хватило», самому приходилось идти нестандартными путями.
Ответ очень простой — я хотел испытать свои силы в хаскеле. Может с готовым получилось бы проще и быстрее, но это не спортивно. :)
Ага. Так если это студенческий интерес, можно пойти дальше и сделать исследовательский проект: сравнить производительность/границы применимости вашего кода на Хаскеле с более стандартными средами типа singular, macaulay2 и пакетами из Maple/Mathematica. Зачем: вам — возможность сказать в своем CV
— я изучил такие-то среды, знаю как работают,
— может даже статью тиснуть,
а кроме того такое сравнение представляет интерес для людей из computer algebra сообщества: там постоянно нужно посчитать что-то большое, на что ресурсов не хватает, и у математиков есть предрассудок (частично обоснованный), что если машина за 5 минут не посчитала, то и смысла возиться нет. Часто возникает мысль «вот взял бы нормальный язык программирования вместо этого DSL внутри Maple и посчиталось бы в разы быстрее», но мало кто пробовал и еще меньше людей о своем опыте рассказывало.
— я изучил такие-то среды, знаю как работают,
— может даже статью тиснуть,
а кроме того такое сравнение представляет интерес для людей из computer algebra сообщества: там постоянно нужно посчитать что-то большое, на что ресурсов не хватает, и у математиков есть предрассудок (частично обоснованный), что если машина за 5 минут не посчитала, то и смысла возиться нет. Часто возникает мысль «вот взял бы нормальный язык программирования вместо этого DSL внутри Maple и посчиталось бы в разы быстрее», но мало кто пробовал и еще меньше людей о своем опыте рассказывало.
А как насчёт аргумента «надо же разобраться, как именно это работает»?
Мне так жаль, что на Хабре Haskell в основном применяется для демонстрации решения абстрактных математических задач…
Прочитал как «Алгоритм бухгалтера» сразу подумал «во до чего техника дошла»
Sign up to leave a comment.
Многочлены от нескольких переменных и алгоритм Бухбергера на Haskell