EP0228915A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method and apparatus for simulating systems described by partial differential equations
Assignee: Thinking Machines Corp
•
Filing: 1986-12-29
•
Granted: —
•
Expires: 2006-12-29
Abstract
Abstract A method and apparatus are disclosed for using cellular automata to simulate systems described by partial differential equations such as those that describe the flow of fluid, diffusion or heat transfer. A two-dimensional space is tessellated into a cellular array of regular hexagons. Flow or diffusion into a cell through each of its six sides from each of its six nearest neighbor cells is represented by a value 1; and any other condition is represented by a value 0. A set of rules specifies the effect of such inward flow in terms of an outward flow through at least some of the same six sides of each cell to its nearest neighbors. Interaction of the flow with a surface or other inhomogeneity is simulated by using a different set of rules to specify the outward flow produced when an inward flow encounters a surface or other inhomogeneity in the cell. Outward flow from one cell is an inward flow into its nearest neighbors; and with the next "tick" of the clock of the model, the cycle repeats itself. Over long periods of time such as tens of thousands of ticks of the clock, this process has been shown to simulate the flow of a real fluid an inclined straight-edge.
Inventors
- 👤 Stephen Wolfram
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-28 19:28
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/20; G06F30/28; G06F2111/00; G06F2111/10
Claims Analysis
Total Claims: 49
Claim 1
Independent Claim
173 words
A method of simulating the flow of fluid through a space comprising the steps of: interconnecting a plurality of digital data processors in an array so that each processor is connected to neighboring processors in said array, each said processor representing a region of said space and implementing a rule that specifies outward flow of fluid from said region in response to inward flow of fluid to said region, said fluid flow being represented by a signal provided from one processor to another, determining with each processor in accordance with said rule signals representing the outward flow of fluid from said region in response to signals representing the inward flow of fluid to said region, said signals representing the outward flow of fluid being provided to neighboring processors as signals representing the inward flow of fluid, and repeating said determining step over a plurality of cycles using as signals representative of inward flow of fluid those signals representing the outward flow of fluid that were determined by neighboring processors in a previous cycle.
Claim 2
Independent Claim
173 words
A method of simulating the flow of fluid through a space comprising the steps of: interconnecting a plurality of digital data processors in an array so that each processor is connected to neighboring processors in said array, each said processor representing a region of said space and implementing a rule that specifies outward flow of fluid from said region in response to inward flow of fluid to said region, said fluid flow being represented by a signal provided from one processor to another, determining with each processor in accordance with said rule signals representing the outward flow of fluid from said region in response to signals representing the inward flow of fluid to said region, said signals representing the outward flow of fluid being provided to neighboring processors as signals representing the inward flow of fluid, and repeating said determining step over a plurality of cycles using as signals representative of inward flow of fluid those signals representing the outward flow of fluid that were determined by neighboring processors in a previous cycle.
Claim 3
Dependent Claim
30 words
The method of claim 1 wherein the digital data processors are connected in a hexagonal array so that a processor is connected to six nearest neighbor processors in the array.
Claim 4
Dependent Claim
46 words
The method of claim 2 wherein the rule that specifies outward flow in response to inward flow requires that the number of outward flows be the same as the number of inward flows and that momentum be conserved unless an obstacle to said flow is encountered.
Claim 5
Dependent Claim
41 words
The method of claim 1 wherein said space is tessellated into a hexagonal array and flow through each hexagon of said array is represented by a six digit number in which each digit represents flow through one side of the hexagon.
Claim 6
Dependent Claim
34 words
The method of claim 4 wherein each digit of the six digit number is a binary digit in which one binary value represents flow and the other binary value represents the absence of flow.
Claim 7
Dependent Claim
47 words
The method of claim 5 wherein the rule that specifies outward flow in response to inward flow requires that the number of outward flows be the same as the number of inward flows and that momentum be conserved unless an obstacle to said flow is encountered .
Claim 8
Dependent Claim
61 words
The method of claim 4 wherein the hexagonal array is subdivided into a group of super cells, said method further comprising the steps of: for each digit position in the six digit number, summing the value of the digits at that position, determining from the sums thus generated a resultant vector, and providing an output signal representative of said resultant vector.
Claim 9
Dependent Claim
51 words
8 . The method of claim 1 wherein the digital data processors are interconnected in an array of n nearest neighbors and flow at each processor in the array is represented by an n digit number in which each digit represents flow between a processor and one of its nearest neighbors.
Claim 10
Dependent Claim
36 words
9 . The method of claim 8 wherein each digit of the n digit number is a binary digit in which one binary value represents flow and the other binary value represents the absence of flow.
Claim 11
Dependent Claim
46 words
The method of claim 8 wherein the rule that specifies outward flow in response to inward flow requires that the number of outward flows be the same as the number of inward flows and that momentum be conserved unless an obstacle to said flow is encountered.
Claim 12
Dependent Claim
60 words
The method of claim 8 wherein the array is divided into a group of super cells, said method further comprising the steps of: for each digit position in the n digit number, summing the value of the digits at that position, determining from the sums thus generated a resultant vector, and providing an output signal representative of said resultant vector.
Claim 13
Dependent Claim
46 words
The method of claim 1 wherein the rule that specifies outward flow in response to inward flow requires that the number of outward flows be the same as the number of inward flows and that momentum be conserved unless an obstacle to said flow is encountered.
Claim 14
Dependent Claim
29 words
The method of claim 1 wherein the rule that specifies outward flow in response to inward flow also specifies the outward flows in the event an obstacle is encountered.
Claim 15
Independent Claim
164 words
A method of simulating the flow of fluid through a space comprising the steps of: representing the space with an array of cellular automata each of which comprises a rule specifying a direction of outward flow of the fluid in response to a direction of inward flow of the fluid in a region of said space, said cellular automata being interconnected along the directions of inward and outward flow so that a specification of a direction of outward flow from one automaton constitutes a specification of a direction of inward flow into an adjacent automaton, representing the flow of fluid into said space by providing an inward flow into at least one cellular automaton at commencement of a simulation, and repeatedly applying the rule over a plurality of cycles to each of the automata of the array using as directions of inward flow of the fluid to an automaton the directions of outward flow of the fluid from adjacent automata in a previous cycle.
Claim 16
Independent Claim
164 words
A method of simulating the flow of fluid through a space comprising the steps of: representing the space with an array of cellular automata each of which comprises a rule specifying a direction of outward flow of the fluid in response to a direction of inward flow of the fluid in a region of said space, said cellular automata being interconnected along the directions of inward and outward flow so that a specification of a direction of outward flow from one automaton constitutes a specification of a direction of inward flow into an adjacent automaton, representing the flow of fluid into said space by providing an inward flow into at least one cellular automaton at commencement of a simulation, and repeatedly applying the rule over a plurality of cycles to each of the automata of the array using as directions of inward flow of the fluid to an automaton the directions of outward flow of the fluid from adjacent automata in a previous cycle.
Claim 17
Dependent Claim
44 words
The method of claim 14 wherein said space is tessellated into a hexagonal array of cellular automata and flow through each hexagon of said array is represented by a six digit number in which each digit represents flow through one side of the hexagon.
Claim 18
Dependent Claim
61 words
The method of claim 15 wherein the hexagonal array is subdivided into a group of super cells, said method further comprising the steps of: for each digit position in the six digit number, summing the value of the digits at that position, determining from the sums thus generated a resultant vector, and providing an output signal representative of said resultant vector.
Claim 19
Dependent Claim
48 words
The method of claim 14 wherein the cellular automata are interconnected in an array of n nearest neighbors and flow at each automaton in the array is represented by an n digit number in which each digit represents flow between an automaton and one of its nearest neighbors.
Claim 20
Dependent Claim
34 words
The method of claim 17 wherein each digit of the n digit number is a binary digit in which one binary value represents flow and the other binary value represents the absence of flow.
Claim 21
Dependent Claim
33 words
The method of claim 17 wherein the the number of outward flows is the same as the number of inward flows and momentum is conserved unless an obstacle to said flow is encountered.
Claim 22
Dependent Claim
59 words
The method of claim 17 wherein the array is divided into a group of super cells, said method further comprising the steps of: for each digit position in the n digit number, summing the value of the digits at that position, determining from the sums'thus generated a resultant vector, and providing an output signal representative of said resultant vector.
Claim 23
Independent Claim
167 words
A method of simulating the solution of a system of partial differential equations in a space of two or three dimensions comprising the steps of: interconnecting a plurality of digital data processors in an array so that each processor is connected to neighboring processors in said array, each said processor representing a region of said space and implementing a rule that specifies outward movement from said region in response to inward movement to said region, said movement being represented by a signal provided from one processor to another, . determining with each processor in accordance with said rule signals representing the outward movement from said region in response to signals representing the inward movement to said region, said signals representing the outward movement being provided to neighboring processors as signals representing the inward movement, and repeating said determining step over a plurality of cycles using as signals representative of inward movement those signals representing the outward movement that were determined by neighboring processors in a previous cycle.
Claim 24
Independent Claim
167 words
A method of simulating the solution of a system of partial differential equations in a space of two or three dimensions comprising the steps of: interconnecting a plurality of digital data processors in an array so that each processor is connected to neighboring processors in said array, each said processor representing a region of said space and implementing a rule that specifies outward movement from said region in response to inward movement to said region, said movement being represented by a signal provided from one processor to another, . determining with each processor in accordance with said rule signals representing the outward movement from said region in response to signals representing the inward movement to said region, said signals representing the outward movement being provided to neighboring processors as signals representing the inward movement, and repeating said determining step over a plurality of cycles using as signals representative of inward movement those signals representing the outward movement that were determined by neighboring processors in a previous cycle.
Claim 25
Independent Claim
159 words
A method of simulating the solution of a system of partial differential equations in a space of two or three dimensions comprising the steps of: representing the space with an array of cellular automata each of which comprises a rule specifying a direction of outward movement in response to a direction of inward movement in a region of said space, said cellular automata being interconnected along the directions of inward and outward movement so that a specification of a direction of outward movement from one automaton constitutes a specification of a direction of inward movement into an adjacent automaton, representing movement into said space by providing an inward movement into at least one cellular automaton at commencement of a simulation, and repeatedly applying the rule over a plurality of cycles to each of the automata of the array using as directions of inward movement to an automaton the directions of outward movement from adjacent automata in a previous cycle.
Claim 26
Independent Claim
159 words
A method of simulating the solution of a system of partial differential equations in a space of two or three dimensions comprising the steps of: representing the space with an array of cellular automata each of which comprises a rule specifying a direction of outward movement in response to a direction of inward movement in a region of said space, said cellular automata being interconnected along the directions of inward and outward movement so that a specification of a direction of outward movement from one automaton constitutes a specification of a direction of inward movement into an adjacent automaton, representing movement into said space by providing an inward movement into at least one cellular automaton at commencement of a simulation, and repeatedly applying the rule over a plurality of cycles to each of the automata of the array using as directions of inward movement to an automaton the directions of outward movement from adjacent automata in a previous cycle.
Claim 27
Independent Claim
185 words
A method of simulating the solutions of a system of partial differential equations in a space of two or- three dimensions comprising the steps of representing the space with an array of multi-digit-numbers each of which digits represents movement at a point in said space in a direction determined by its position in the number, interrelating said numbers along the directions of movement between said points in space so that a specification of a direction of outward movement from one number constitutes a specification of inward movement to an adjacent number, calculating movement between adjacent points in said space in accordance with a rule that specifies a direction of outward movement from a point in response to a direction of inward movement to said point, representing movement into said space by providing an inward movement into at least one point in said space, and repeatedly applying the rule over a plurality of cycles to each of the numbers of the array using as directions of inward movement to a point the directions of outward movement specified in the numbers associated with adjacent points in space.
Claim 28
Independent Claim
185 words
A method of simulating the solutions of a system of partial differential equations in a space of two or- three dimensions comprising the steps of representing the space with an array of multi-digit-numbers each of which digits represents movement at a point in said space in a direction determined by its position in the number, interrelating said numbers along the directions of movement between said points in space so that a specification of a direction of outward movement from one number constitutes a specification of inward movement to an adjacent number, calculating movement between adjacent points in said space in accordance with a rule that specifies a direction of outward movement from a point in response to a direction of inward movement to said point, representing movement into said space by providing an inward movement into at least one point in said space, and repeatedly applying the rule over a plurality of cycles to each of the numbers of the array using as directions of inward movement to a point the directions of outward movement specified in the numbers associated with adjacent points in space.
Claim 29
Dependent Claim
173 words
Apparatus for simulating the flow of fluid through a space comprising: a plurality of digital data processors interconnected in an array so that each processor is connected to neighboring processors in said array, each said processor representing a region of said space and implementing a rule that specifies outward flow of fluid from said region in response to inward flow of fluid to said region, said fluid flow being represented by a signal provided from one processor to another, means for generating with each processor in accordance with said rule signals representing the outward flow of fluid from said region in response to signals representing the inward flow of fluid to said region, said signals representing the outward flow of fluid being provided to neighboring processors as signals representing the inward flow of fluid, and means for repeating said generating step over a plurality of cycles using as signals representative of inward flow of fluid those signals representing the outward flow of fluid that were determined by neighboring processors in a previous cycle.
Claim 30
Dependent Claim
173 words
Apparatus for simulating the flow of fluid through a space comprising: a plurality of digital data processors interconnected in an array so that each processor is connected to neighboring processors in said array, each said processor representing a region of said space and implementing a rule that specifies outward flow of fluid from said region in response to inward flow of fluid to said region, said fluid flow being represented by a signal provided from one processor to another, means for generating with each processor in accordance with said rule signals representing the outward flow of fluid from said region in response to signals representing the inward flow of fluid to said region, said signals representing the outward flow of fluid being provided to neighboring processors as signals representing the inward flow of fluid, and means for repeating said generating step over a plurality of cycles using as signals representative of inward flow of fluid those signals representing the outward flow of fluid that were determined by neighboring processors in a previous cycle.
Claim 31
Dependent Claim
30 words
The apparatus of claim 24 wherein the digital data processors are connected in a hexagonal array so that a processor is connected to six nearest neighbor processors in the array.
Claim 32
Dependent Claim
46 words
The apparatus of claim 25 wherein the rule that specifies outward flow in response to inward flow requires that the number of outward flows be the same as the number of inward flows and that momentum be conserved unless an obstacle to said flow is encountered.
Claim 33
Dependent Claim
41 words
The apparatus of claim 24 wherein said space is tessellated into a hexagonal array and flow through each hexagon of said array is represented by a six digit number in which each digit represents flow through one side of the hexagon.
Claim 34
Dependent Claim
34 words
The apparatus of claim 27 wherein each digit of the six digit number is a binary digit in which one binary value represents flow and the other binary value represents the absence of flow.
Claim 35
Dependent Claim
50 words
2 9 . The aparatus of claim 28 wherein the rule that specifies outward flow in response to inward flow requires that the number of outward flows be the same as the number of inward flows and that momentum be conserved unless an obstacle to said flow is encountered .
Claim 36
Dependent Claim
61 words
The apparatus of claim 27 wherein the hexagonal array is subdivided into a group of super cells, said apparatus further comprising: means for summing the value of the digits at each digit position in the six digit number, means for determining from the sums thus generated a resultant vector, and means for providing an output signal representative of said resultant vector.
Claim 37
Dependent Claim
52 words
31 . The apparatus method of claim 24 wherein the digital data processors are interconnected in an array of n nearest neighbors and flow at each processor in the array is represented by an n digit number in which each digit represents flow between a processor and one of its nearest neighbors.
Claim 38
Dependent Claim
34 words
The apparatus of claim 31 wherein each digit of the n digit number is a binary digit in which one binary value represents flow and the other binary value represents the absence of flow.
Claim 39
Dependent Claim
46 words
The apparatus of claim 31 wherein the rule that specifies outward flow in response to inward flow requires that the number of outward flows be the same as the number of inward flows and that momentum be conserved unless an obstacle to said flow is encountered.
Claim 40
Dependent Claim
60 words
The apparatus of claim 31 wherein the array is divided into a group of super cells, said apparatus further comprising: means for summing the value of the digits at each digit position in the n digit number, means for determining from the sums thus generated a resultant vector, and means for providing an output signal representative of said resultant vector.
Claim 41
Dependent Claim
46 words
The apparatus of claim 24 wherein the rule that specifies outward flow in response to inward flow requires that the number of outward flows be the same as the number of inward flows and that momentum be conserved unless an obstacle to said flow is encountered.
Claim 42
Dependent Claim
160 words
Apparatus for simulating the flow of fluid through a space comprising: an array of cellular automata each of which comprises a rule specifying a direction of outward flow of the fluid in response to a direction of inward flow of the fluid in a region of said space, said cellular automata being interconnected along the directions of inward and outward flow so that a specification of a direction of outward flow from one automaton constitutes a specification of a direction of inward flow into an adjacent automaton, means for representing the flow of fluid into said space by providing an inward flow into at least one cellular automaton at commencement of a simulation, and means for repeatedly applying the rule over a plurality of cycles to each of the automata of the array using as directions of inward flow of the fluid to an automaton the directions of outward flow of the fluid from adjacent automata in a previous cycle.
Claim 43
Dependent Claim
160 words
Apparatus for simulating the flow of fluid through a space comprising: an array of cellular automata each of which comprises a rule specifying a direction of outward flow of the fluid in response to a direction of inward flow of the fluid in a region of said space, said cellular automata being interconnected along the directions of inward and outward flow so that a specification of a direction of outward flow from one automaton constitutes a specification of a direction of inward flow into an adjacent automaton, means for representing the flow of fluid into said space by providing an inward flow into at least one cellular automaton at commencement of a simulation, and means for repeatedly applying the rule over a plurality of cycles to each of the automata of the array using as directions of inward flow of the fluid to an automaton the directions of outward flow of the fluid from adjacent automata in a previous cycle.
Claim 44
Dependent Claim
166 words
Apparatus for simulating the solution of a system of partial differential equations in a space of two or three dimensions comprising: a plurality of digital data processors interconnected in an array so that each processor is connected to neighboring processors in said array, each said processor representing a region of said space and implementing a rule that specifies outward movement from said region in response to inward movement to said region, said movement being represented by a signal provided from one processor to another, means for generating with each processor in accordance with said rule signals representing the outward movement from said region in response to signals representing the inward movement to said region, said signals representing the outward movement being provided to neighboring processors as signals representing the inward movement, and means for repeating said generating step over a plurality of cycles using as signals representative of inward movement those signals representing the outward movement that were determined by neighboring processors in a previous cycle.
Claim 45
Dependent Claim
166 words
Apparatus for simulating the solution of a system of partial differential equations in a space of two or three dimensions comprising: a plurality of digital data processors interconnected in an array so that each processor is connected to neighboring processors in said array, each said processor representing a region of said space and implementing a rule that specifies outward movement from said region in response to inward movement to said region, said movement being represented by a signal provided from one processor to another, means for generating with each processor in accordance with said rule signals representing the outward movement from said region in response to signals representing the inward movement to said region, said signals representing the outward movement being provided to neighboring processors as signals representing the inward movement, and means for repeating said generating step over a plurality of cycles using as signals representative of inward movement those signals representing the outward movement that were determined by neighboring processors in a previous cycle.
Claim 46
Dependent Claim
157 words
3 8. Apparatus for simulating the solution of a system of partial differential equations in a space of two or three dimensions comprising: an array of cellular automata each of which comprises a rule specifying a direction of outward movement in response to a direction of inward movement in a region of said space, said cellular automata being interconnected along the directions of inward and outward movement so that a specification of a direction of outward movement from one automaton constitutes a specification of a direction of inward movement into an adjacent automaton, means for representing movement into said space by providing an inward movement into at least one cellular automaton at commencement of a simulation, and means for repeatedly applying the rule over a plurality of cycles to each of the automata of the array using as directions of inward movement to an automaton the directions of outward movement from adjacent automata in a previous cycle.
Claim 47
Dependent Claim
157 words
3 8. Apparatus for simulating the solution of a system of partial differential equations in a space of two or three dimensions comprising: an array of cellular automata each of which comprises a rule specifying a direction of outward movement in response to a direction of inward movement in a region of said space, said cellular automata being interconnected along the directions of inward and outward movement so that a specification of a direction of outward movement from one automaton constitutes a specification of a direction of inward movement into an adjacent automaton, means for representing movement into said space by providing an inward movement into at least one cellular automaton at commencement of a simulation, and means for repeatedly applying the rule over a plurality of cycles to each of the automata of the array using as directions of inward movement to an automaton the directions of outward movement from adjacent automata in a previous cycle.
Claim 48
Dependent Claim
187 words
Apparatus for simulating the solutions of a system of partial differential equations in a space of two or three dimensions comprising: means for storing an array of multi-digit-numbers each of which digits represents movement at a point in said space in a direction determined by its position in the number, said numbers being interrelated along the directions of movement between said points in space so that a specification of a direction of outward movement from one number constitutes a specification of inward movement to an adjacent number, means for calculating movement between adjacent points in said space in accordance with a rule that specifies a direction of outward movement from a point in response to a direction of inward movement to said point, means for representing movement into said space by providing an inward movement into at least one point in said space, and means for repeatedly applying the rule over a plurality of cycles to each of the numbers of the array using as directions of inward movement to a point the directions of outward movement specified in the numbers associated with adjacent points in space.
Claim 49
Dependent Claim
187 words
Apparatus for simulating the solutions of a system of partial differential equations in a space of two or three dimensions comprising: means for storing an array of multi-digit-numbers each of which digits represents movement at a point in said space in a direction determined by its position in the number, said numbers being interrelated along the directions of movement between said points in space so that a specification of a direction of outward movement from one number constitutes a specification of inward movement to an adjacent number, means for calculating movement between adjacent points in said space in accordance with a rule that specifies a direction of outward movement from a point in response to a direction of inward movement to said point, means for representing movement into said space by providing an inward movement into at least one point in said space, and means for repeatedly applying the rule over a plurality of cycles to each of the numbers of the array using as directions of inward movement to a point the directions of outward movement specified in the numbers associated with adjacent points in space.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.