СПОСОБ И СИСТЕМА ДЛЯ ОПРЕДЕЛЕНИЯ КОНФИГУРАЦИИ МОДЕЛИ, СОДЕРЖАЩЕЙ СОВОКУПНОСТЬ ЭЛЕМЕНТОВ И УДОВЛЕТВОРЯЮЩЕЙ НАБОРУ ОГРАНИЧЕНИЙ

1. Способ определения конфигурации модели, содержащей совокупность элементов, удовлетворяющих набору ограничений, включающий в себя следующие действия:
(a) задание совокупности элементов и набора ограничений, причем совокупность элементов представлена множеством переменных, а каждое ограничение соответствует, по меньшей мере, одному уравнению ограничения, взаимосвязанному с подмножеством этого множества переменных;
(b) формирование, по меньшей мере, одного дерева, содержащего множество узлов, причем это, по меньшей мере, одно дерево содержит корневой узел, имеющий, по меньшей мере, один дочерний узел, при этом узлы, имеющие, по меньшей мере, один дочерний узел, определены как родительские узлы, узлы, не имеющие дочерних узлов, определены как листьевые узлы и каждый узел соответствует подмножеству уравнений ограничений;
(c) параллельное решение уравнений ограничений всех листьевых узлов из подмножества листьевых узлов;
(d) решение уравнений ограничений каждого родительского узла, у которого уже решены уравнения ограничений всех дочерних узлов, на основе решений уравнений ограничений соответствующих дочерних узлов;
(e) повторение действия (d) до тех пор, пока не будут решены уравнения ограничений корневого узла;
(f) распространение решений уравнений ограничений каждого родительского узла на соответствующие дочерние узлы каждого родительского узла с определением тем самым конфигурации модели, удовлетворяющей заданному набору ограничений; и
(g) выдача элементов, соответствующих этой определенной конфигурации.
2. Способ по п. 1, дополнительно включающий в себя:
(h) обеспечение модуля вывода на дисплей; и
(i) вывод на дисплей выдаваемых элементов, соответствующих этой определенной конфигурации модели, удовлетворяющей заданному набору ограничений.
3. Способ по п. 1, в котором решение уравнений ограничений каждого дочернего узла включает в себя:
(ii) обновление вектора состояния дочернего узла; и
(iii) формирование обновленной статистической матрицы, соответствующей обновленному вектору состояния.
4. Способ по п. 3, в котором обновление вектора состояния каждого дочернего узла основано на различии между первой конфигурацией, в которой уравнения ограничений, соответствующие дочернему узлу, не решены, и второй конфигурацией, в которой уравнения ограничений, соответствующие дочернему узлу, решены.
5. Способ по п. 3, в котором решение уравнений ограничений каждого родительского узла включает в себя:
(iv) предсказание вектора состояния каждого дочернего узла этого родительского узла, соответствующего обновленному вектору состояния каждого дочернего узла этого родительского узла; и
(v) формирование предсказанной статистической матрицы, соответствующей каждому пересказанному вектору состояния.
6. Способ по п. 5, в котором решение уравнений ограничений каждого родительского узла дополнительно включает в себя:
(vi) комбинирование предсказанных статистических матриц дочерних узлов этого родительского узла в единую комбинированную статистическую матрицу;
(vii) формирование комбинированного вектора состояния, соответствующего комбинированной статистической матрице; и
(viii) обновление вектора состояния этого родительского узла на основе комбинированной статистической матрицы и комбинированного вектора состояния.
7. Способ по п. 6, в котором распространение решений уравнений ограничений каждого родительского узла включает в себя:
(ix) распространение обновленного вектора состояния этого родительского узла на каждый дочерний узел этого родительского узла для уточнения обновленных векторов состояния всех дочерних узлов этого родительского узла; и
(x) повторение действия (ix) до тех пор, пока не будут уточнены векторы состояния листьевых узлов.
8. Способ по п. 1, дополнительно включающий в себя повторение действий (c)-(f) до тех пор, пока не будет выполнено первое условие точности.
9. Способ по п. 8, в котором повторение носит итеративный характер.
10. Способ по п. 8, в котором первое условие точности основано на векторе невязки.
11. Способ по п. 1, в котором элементы представляют собой геометрические примитивы.
12. Способ по п. 11, в котором геометрические примитивы представляют собой двумерные геометрические примитивы.
13. Способ по п. 11, в котором геометрические примитивы представляют собой трехмерные геометрические примитивы.
14. Способ по п. 1, дополнительно включающий в себя формирование матричного представления модели, в котором матрица имеет первую размерность и вторую размерность, при этом каждый из, по меньшей мере, одного вектора первой размерности матрицы соответствует подмножеству из множества переменных, матрица разрежена по первой размерности и каждый узел, по меньшей мере, одного дерева соответствует, по меньшей мере, одному вектору первой размерности матрицы.
15. Способ по п. 14, в котором модель представляет собой нелинейную модель.
16. Способ по п. 15, в котором формирование матричного представления нелинейной модели включает в себя:
(xi) линеаризацию нелинейной модели для получения линейной модели до действия (b); и
(xii) повторение действий (c)-(f) до тех пор, пока не будет выполнено второе условие точности.
17. Способ по п. 16, в котором повторение носит итеративный характер.
18. Способ по п. 16, в котором второе условие точности основано на векторе невязки.
19. Способ по п. 15, в котором матрица представляет собой последовательно линеаризованную матрицу.
20. Способ по п. 1, в котором формирование, по меньшей мере, одного дерева включает в себя:
(xiii) создание корневого узла этого дерева и размещение, по меньшей мере, одного уравнения ограничения в этом корневом узле; и
(xiv) размещение уравнений ограничений, имеющих, меньшей мере, одну общую переменную с, по меньшей мере, одним уравнением ограничения этого корневого узла, в соответствующих дочерних узлах этого корневого узла.
21. Способ по п. 20, в котором формирование, по меньшей мере, одного дерева дополнительно включает в себя:
(xv) размещение уравнений ограничений, имеющих, меньшей мере, одну общую переменную с, по меньшей мере, одним уравнением ограничения соответствующих дочерних узлов, в дополнительных соответствующих дочерних узлах этих соответствующих дочерних узлов;
(xvi) повторение действия (xv) до тех пор, пока каждое уравнение ограничения не будет размещено в, по меньшей мере, одном узле, по меньшей мере, одного дерева.
22. Способ по п. 1, в котором модель имеет, по меньшей мере, одну степень свободы.
23. Способ по п. 1, дополнительно включающий в себя:
(xvii) получение в качестве входных данных пользователя команды на изменение, по меньшей мере, одного элемента из совокупности элементов; и
(xviii) в ответ на входные данные пользователя решение системы уравнений ограничений для определения новой конфигурации модели.
24. Способ по п. 23, дополнительно включающий в себя выдачу элементов, соответствующих конфигурации модели, удовлетворяющей набору ограничений.
25. Способ по п. 1, в котором решение уравнений ограничений родительского узла, основанное на решении уравнений ограничений соответствующих дочерних узлов, выполняется параллельно.
26. Способ по любому из пп. 3, 5 или 6, в котором статистическая матрица представляет собой ковариационную матрицу.
27. Способ по п. 1, в котором подмножество листьевых узлов включает в себя все листьевые узлы.
28. Система для определения конфигурации модели, содержащей совокупность элементов и набор ограничений, в программируемом вычислительном устройстве, причем совокупность элементов представлена множеством переменных, каждое ограничение соответствует, по меньшей мере, одному уравнению ограничения, взаимосвязанному с подмножеством этого множества переменных, при этом система содержит, по меньшей мере, один процессор и, по меньшей мере, одно пользовательское устройство ввода и выполнена с возможностью:
(a) получения входных данных пользователя посредством, по меньшей мере, одного устройства ввода для формирования модели;
(b) формирования, по меньшей мере, одного дерева, содержащего множество узлов, причем это, по меньшей мере, одно дерево содержит корневой узел, имеющий, по меньшей мере, один дочерний узел, при этом узлы, имеющие, по меньшей мере, один дочерний узел, определены как родительские узлы, узлы, не имеющие дочерних узлов, определены как листьевые узлы и каждый узел соответствует подмножеству уравнений ограничений;
(c) параллельного решения уравнений ограничений всех листьевых узлов из подмножества листьевых узлов;
(d) решения уравнений ограничений каждого родительского узла, у которого уже решены уравнения ограничений всех дочерних узлов, на основе решений уравнений ограничений соответствующих дочерних узлов;
(e) повторения действия (d) до тех пор, пока не будут решены уравнения ограничений корневого узла;
(f) распространения решений уравнений ограничений каждого родительского узла на соответствующие дочерние узлы каждого родительского узла с определением тем самым конфигурации модели, удовлетворяющей заданному набору ограничений; и
(g) выдачи элементов, соответствующих этой определенной конфигурации.
29. Система по п. 28, дополнительно содержащая, по меньшей мере, один дисплей и дополнительно выполненная с возможностью вывода на, по меньшей мере, один дисплей выдаваемых элементов этой определенной конфигурации.
30. Система по п. 28, дополнительно выполненная с возможностью:
(h) получения входных данных пользователя для изменения, по меньшей мере, одного элемента из совокупности элементов; и
(i) решения системы уравнений ограничений для определения новой конфигурации модели.
31. Система для определения конфигурации модели, содержащей совокупность элементов и набор ограничений, в программируемом вычислительном устройстве, причем совокупность элементов представлена множеством переменных, каждое ограничение соответствует, по меньшей мере, одному уравнению ограничения, взаимосвязанному с подмножеством этого множества переменных, а система содержит память, по меньшей мере, один процессор, по меньшей мере, одно пользовательское устройство ввода, по меньшей мере, один дисплей, и компьютерную модель, сохраненную в памяти системы, при этом система выполнена с возможностью:
(a) получения входных данных пользователя посредством, по меньшей мере, одного устройства ввода для изменения, по меньшей мере, одного элемента этой совокупности элементов;
(b) формирования, по меньшей мере, одного дерева, содержащего множество узлов, причем это, по меньшей мере, одно дерево содержит корневой узел, имеющий, по меньшей мере, один дочерний узел, при этом узлы, имеющие, по меньшей мере, один дочерний узел, определены как родительские узлы, узлы, не имеющие дочерних узлов, определены как листьевые узлы и каждый узел соответствует подмножеству уравнений ограничений;
(c) параллельного решения уравнений ограничений всех листьевых узлов из подмножества листьевых узлов;
(d) решения уравнений ограничений каждого родительского узла, у которого уже решены уравнения ограничений всех дочерних узлов, на основе решений уравнений ограничений соответствующих дочерних узлов;
(e) повторения действия (d) до тех пор, пока не будут решены уравнения ограничений корневого узла;
(f) распространения решений уравнений ограничений каждого родительского узла на соответствующие дочерние узлы каждого родительского узла с определением тем самым конфигурации модели, удовлетворяющей заданному набору ограничений;
(g) выдачи элементов, соответствующих этой определенной конфигурации; и
(h) вывода на, по меньшей мере, один дисплей выдаваемых элементов этой определенной конфигурации.
32. Постоянный машиночитаемый носитель информации, содержащий машиночитаемый код, включающий в себя программный код, реализующий способ определения конфигурации модели, содержащей совокупность элементов, удовлетворяющих набору ограничений, включающий в себя следующие действия:
(a) задание совокупности элементов и набора ограничений, причем совокупность элементов представлена множеством переменных, а каждое ограничение соответствует, по меньшей мере, одному уравнению ограничения, взаимосвязанному с подмножеством этого множества переменных;
(b) формирование, по меньшей мере, одного дерева, содержащего множество узлов, причем это, по меньшей мере, одно дерево содержит корневой узел, имеющий, по меньшей мере, один дочерний узел, при этом узлы, имеющие, по меньшей мере, один дочерний узел, определены как родительские узлы, узлы, не имеющие дочерних узлов, определены как листьевые узлы и каждый узел соответствует подмножеству уравнений ограничений;
(c) параллельное решение уравнений ограничений всех листьевых узлов из подмножества листьевых узлов;
(d) решение уравнений ограничений каждого родительского узла, у которого уже решены уравнения ограничений всех дочерних узлов, на основе решений уравнений соответствующих дочерних узлов;
(e) повторение действия (d) до тех пор, пока не будут решены уравнения ограничений корневого узла;
(f) распространение решений уравнений ограничений каждого родительского узла на соответствующие дочерние узлы каждого родительского узла с определением тем самым конфигурации модели, удовлетворяющей заданному набору ограничений; и
(g) выдача элементов, соответствующих этой определенной конфигурации.