Dynamic updating of a force approximation data model
Inventors
Assignees
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-11568106-B1
Publication Date
2023-01-31
Expiration Date
Abstract
One example method of operation may include creating a force approximation of a number of nodes in a defined space at an initial time (t0), the force approximation being based on a data realization simulation model of an n-body simulation, where n is an integer greater than one. The method may also include determining initial displacement changes of one or more of the nodes within the defined space has occurred in the force approximation, summing the initial displacement changes of the one or more of the nodes to create a summed total displacement, creating an initial displacement threshold (Td) based on the summed total displacement. At a later time (t1), determining additional displacement changes of one or more of the nodes have occurred, summing the additional displacement changes of the one or more of the nodes to create a new summed total displacement, comparing the new summed total displacement to the summed total displacement, and determining whether to create a new force approximation based on the comparison of the new summed total displacement to the summed total displacement.
Core Innovation
The disclosed dynamic force-approximation update technique maintains a force approximation for a plurality of nodes in a defined space based on an n-body simulation data realization model. A Barnes-Hut (quadtree) force approximation is created at an initial time (t0), and changes in node displacement within the defined space are detected within the force approximation.
Initial displacement changes are summed to create a summed total displacement, and an initial displacement threshold (Td) is derived from the summed total displacement. At a later time (t1), additional displacement changes are accumulated and summed to form a new summed total displacement, which is then compared to the previous summed displacement/threshold to decide whether to create a new force approximation or reuse the existing one.
The approach specifies algorithmic logic for maintaining and resetting a running displacement sum and for monitoring function and logic flow that determine approximation cycles. The description states that this reduces the number of quadtree recalculations while still requiring displacement summation, and it reports experiment results of up to about 51% runtime reduction and a median of about 18% (with a worst case of about 6%), including figure-based demonstrations using example graphs.
Claims Coverage
The document provides three independent claim sets (method, apparatus, and non-transitory computer readable storage medium) covering the same core workflow with a shared inventive concept: dynamic creation or reuse of a force approximation in an n-body simulation by summing displacement changes and deciding on whether a new force approximation is needed based on additional displacement summation.
Dynamic creation or reuse of a force approximation based on summed displacement changes
creating a force approximation of a plurality of nodes in a defined space at an initial time (t0), the force approximation being based on a data realization simulation model of an n-body simulation; determining that initial displacement changes of one or more of the plurality of nodes within the defined space has occurred in the force approximation; summing the initial displacement changes of the one or more of the plurality of nodes to create a summed total displacement; and based on a summation of additional displacement changes of one or more of the plurality of nodes, determining whether to create a new force approximation.
Barnes-Hut force approximation for updating n-body node forces
the force approximation uses a Barnes-Hut approximation.
Threshold-based determination for whether a new force approximation is created
creating an initial displacement threshold from a summed total displacement; determining additional displacement changes of one or more of the plurality of nodes at a later time and summing those additional displacement changes to form a new summed total displacement; and comparing the new summed total displacement to the initial displacement threshold to determine whether the new total is greater than or equal to the threshold.
Update of displacement threshold and reset of accumulated displacement after a trigger
setting a new displacement threshold equal to the new summed total displacement and resetting a current summed total value of displacement to zero when the new summed total displacement is greater than or equal to the initial displacement threshold.
Iterative accumulation over continuing time intervals before updating
when a current summed total value of displacement over a specified number of continuing time intervals reaches or exceeds a new displacement threshold, the new displacement threshold is updated to the current summed total.
Across the independent claim sets, the inventive coverage centers on dynamically deciding whether to create a new force approximation versus reuse an existing one. This decision is driven by summing initial and additional displacement changes in a defined space for an n-body simulation model, optionally using Barnes-Hut and threshold-based update logic, including state updates and multi-interval accumulation.
Stated Advantages
Reduces the number of quadtree recalculations while still requiring displacement summation.
Up to about 51% runtime reduction (with a median of about 18% and a worst case of about 6%).
Documented Applications
Applied to spring-electric graph layouts using a dynamic Barnes-Hut/quadtree force approximation update technique.
Demonstrated using example graphs KONECT and SUITESPARSE.
Potential use in other approximation models and application domains is stated.
A representative computing architecture is described, including a computer system/server architecture with memory, processor, and a non-transitory computer readable medium.
Interested in licensing this patent?