Проблемы с производительностью: Решение неравенства с несколькими предположениями в системе Mathematica

Мне нужно доказать неравенство (или найти контрпример) с учетом нескольких предположений (также неравенств). К сожалению, доказываемое неравенство представляет собой довольно длинное и сложное выражение. Имеется около 15 переменных, и вывод FullSimplify занимает несколько страниц формата A4. Для примеров с меньшим количеством переменных FindInstance помогает найти контрпример или дает результат {}, если неравенство верно. Я также пытался использовать Reduce таким образом:

Reduce[
   Implies[
      assumtion1 && assumtion2,
      inequality
   ],
   Reals
]

Для простых примеров это выводит «Истина», если неравенство выполняется. Но в моем случае после нескольких часов работы Mathematica потребовалось 5-6 ГБ оперативной памяти (и подкачка), поэтому мне пришлось прервать процесс.

Могу ли я что-нибудь сделать с Mathematica для повышения производительности?


inequalities wolfram-mathematica inequality
person lumbric    schedule 11.12.2011    source источник
comment
То, что вы делаете, является подмножеством исключения квантификатора, см. mathworld.wolfram.com/QuantifierElimination.html. , и это имеет двойную экспоненциальную сложность в наихудших сценариях...   -  person Per Alexandersson    schedule 11.12.2011
comment
Какова форма этих двух предположений?   -  person rcollyer    schedule 12.12.2011
comment
Ну, есть более 2 предположений. Предположения тоже являются неравенствами, и если быть точным, у меня их 32. Все неравенства и неравенства, которые мне нужно доказать, содержат 28 различных переменных. Я полагаю, @Paxinum уже дал правильный ответ, почему это просто невозможно решить таким образом. Я надеялся, что есть какое-то другое решение, но у меня закончились идеи. Я также был бы рад любым вдохновляющим подсказкам, как продолжить работу над этим... :) Могу ли я что-нибудь сделать, чтобы решить эту проблему, или было бы лучше, если бы я попытался найти другой способ с меньшим количеством переменных?   -  person lumbric    schedule 12.12.2011
comment
Вы можете попробовать преобразовать импликацию в форму !P \[Or] Q. Не знаю, поможет ли, но может.   -  person rcollyer    schedule 12.12.2011
comment
Объедините то, что я сказал выше, с LogicalExpand и, возможно, добавьте к этому Simplify. В этот момент вы, возможно, сможете разделить свои неравенства на непересекающиеся подмножества. В основном это всего лишь предположение, но оно у меня работало в прошлом.   -  person rcollyer    schedule 12.12.2011
comment
Мне удалось сократить все до 11 переменных вручную. Но к сожалению и с LogicalExpand нет возможности получить результат. LogicalExpand просто переводит все в ту форму, которую вы предложили в своем комментарии ранее. Это означает, что в основном у меня есть много неравенств с одной переменной (они исходят из предположений, у меня есть границы для большинства переменных) и одно неравенство со всеми переменными. Я не думаю, что существуют непересекающиеся подмножества неравенств.   -  person lumbric    schedule 13.12.2011
comment
Я думаю, что без получения более подробной информации люди не смогут вам помочь. Можете ли вы предоставить более подробную информацию о проблеме, на которую вы смотрите? (Если код очень длинный, вставьте его на pastebin.com или gist.github.com и т. д.)   -  person Simon    schedule 19.12.2011
comment
Это несколько раз встречалось в MathGroup, и ответ всегда был одинаковым: алгоритм, который использует Mathematica, имеет двойную экспоненциальную сложность по количеству переменных. Теперь я не знаком с математикой этого, но есть большая вероятность, что решения не будет. Что вы обязательно должны сделать, так это опубликовать несколько примеров того, с чем вы работаете: возможно, у них есть какое-то особое свойство, которое позволит найти другое решение. Но, как сказал Паксинум: маловероятно, что Reduce можно ускорить.   -  person Szabolcs    schedule 19.12.2011
comment
Кроме того, я думаю, вам больше нравится искать экспертов по теме либо в math.SE, либо в MathOverflow. Но тогда вам, вероятно, нужно перефразировать свой вопрос и спросить о том, какие быстрые алгоритмы существуют для решения конкретных (не общих) неравенств, с которыми вы имеете дело. (Но опять же, я не знаком с математикой этого, так что могу ошибаться.)   -  person Szabolcs    schedule 19.12.2011
comment
@lumbric Людям может быть трудно ответить, не имея ничего общего ... не могли бы вы дать ссылку на свой блокнот или показать меньший пример, который заставляет MMA зависать?   -  person abcd    schedule 19.12.2011
comment
Извините, я не могу предоставить полезный комментарий, но я просто скажу, что мой опыт работы с Mathematica значительно улучшился, когда я вставил в компьютер еще 8 ГБ памяти в дополнение к 4 ГБ, которые у меня уже есть. Теперь Mathematica падает вдвое реже...   -  person cormullion    schedule 22.12.2011
comment
@cormullion Хммм ... утроение памяти уменьшило количество сбоев только вдвое? Мма гораздо хуже пожирает память, чем я думал;)   -  person abcd    schedule 22.12.2011
comment
@yoda :) да, теперь Mathematica быстрее возвращает результаты, и поэтому я быстрее в конечном итоге набираю что-то глупое и вылетаю...   -  person cormullion    schedule 22.12.2011
comment
Какие предположения/неравенства у вас есть? (линейный/полиномиальный/тригонометрический/экспоненциальный/и т.д.)   -  person user1071136    schedule 26.12.2011

Ответы (1)


arrow_upward
4
arrow_downward

Вы найдете очень хорошую статью об алгоритмах Mma CAD здесь

Цилиндрическая алгебраическая декомпозиция (CAD), которую использует Mma, масштабируется с двойной экспоненциальной зависимостью от количества переменных.

Более новые методы имеют двойную экспоненту по количеству чередований квантификаторов.

Я думаю, вам не повезет, используя только внутренний движок Mma, но вы можете свернуть свой собственный, исходя из симметрии вашей проблемы (если она есть).

person Dr. belisarius    schedule 26.12.2011
comment
Цитаты за Новые методы имеют двойную экспоненциальную зависимость от количества количественных изменений? - person Mr.Wizard; 27.12.2011
comment
@Мистер. Например, второй абзац здесь usna.edu/Users/ cs/wcbrown/research/qebycad/Tutorial/node2.html - person Dr. belisarius; 27.12.2011