# US 2014/0207426 A1 · Simulation of phenomena characterized by partial differential equations

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2014/0207426 A1
- Document ID: US20140207426A1
- Status: Published application
- Kind: A1
- Application number: 13/744,999
- Filed: 2013-01-18
- Published: 2014-07-24
- Earliest claimed: 2013-01-18
- Assignees: The Board of Trustees of the Leland Stanford Junior University
- Inventors: Wonseok Shin; Shanhui Fan
- Web page: https://patentgrep.com/patent/US20140207426A1

## CPC

- G06F 30/23: using finite element methods [FEM] or finite difference methods [FDM]
- G06F 30/20: Design optimisation, verification or simulation (optimisation, verification or simulation of circuit designs G06F30/30)
- G06F 2111/10: Numerical modelling
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Various aspects of the present disclosure are directed toward apparatus, methods, and articles of manufacture for simulating a physical phenomenon characterized by a set of partial differential equations that are reduced based on harmonic time dependence. The system of linear equations represent an operation in the differential equations, and are characterized by a coefficient matrix multiplied by an unknown column vector, with the product thereof being equal to a column vector. The system of linear equations is solved using at least one of three sets of operations.

## Claims

### Claim 1

An apparatus for simulating a physical phenomenon characterized by a set of partial differential equations that are reduced based on harmonic time dependence, the apparatus comprising:
a data computing circuit having
stored therefor a system of linear equations representing an operation in the differential equations and in which a coefficient matrix is multiplied by an unknown column vector and with the product thereof being equal to a column vector, and
stored therein a program for executing an algorithm which, when executed, solves the system of linear equations, wherein the algorithm sets forth at least one of the following three sets of operations:
(i) multiplying the coefficient matrix by left and right scale-factor preconditioning matrices, and multiplying the column vector by the left scale-factor preconditioning matrix, each matrix including at least one of: entries of scale factors and combinations of scale factors of a perfectly matched layer,
(ii) symmetrizing the coefficient matrix by multiplying the coefficient matrix by left and right diagonally-dominant preconditioning matrices while maintaining a condition number of the coefficient matrix within an order of magnitude of a condition number of the matrix prior to symmetrizing, and
(iii) confining a majority of eigenvalues of the coefficient matrix in a half-plane having a boundary that crosses an origin of a complex plane.

### Claim 2 (depends on 1)

The apparatus of claim 1, wherein the data computing circuit is configured and arranged to
receive data characterizing the physical phenomenon, and
use the program to execute the algorithm, using the received data as an input, to solve the system of linear equations and generate an output that characterizes the physical phenomenon.

### Claim 3 (depends on 2)

The apparatus of claim 2, wherein the data computing circuit is configured and arranged to execute the algorithm to solve the linear equations by at least one of:
executing the algorithm with received electromagnetic wave data to solve the linear equations and generate an output that characterizes the behavior of the electromagnetic wave;
executing the algorithm with received optical wave data to solve the linear equations and generate an output that characterizes behavior of the optical wave;
executing the algorithm with received fluid dynamics system data to solve the linear equations and generate an output that characterizes behavior of the fluid dynamics system;
executing the algorithm with received chemical reaction data to solve the linear equations and generate an output that characterizes behavior of the chemical reaction; and
executing the algorithm with received mechanical system data to solve the linear equations and generate an output that characterizes behavior of the mechanical system.

### Claim 4 (depends on 1)

The apparatus of claim 1, wherein the algorithm sets forth at least two of the sets of operations.

### Claim 5 (depends on 1)

The apparatus of claim 1, wherein the algorithm sets forth all of the sets of operations.

### Claim 6 (depends on 1)

The apparatus of claim 1, wherein the algorithm sets forth the operation of confining the majority of eigenvalues of the coefficient matrix in the half-plane, and thereafter, the operation of at least one of the steps of multiplying the coefficient matrix by the left and right scale-factor preconditioning matrices and symmetrizing the coefficient matrix.

### Claim 7 (depends on 1)

The apparatus of claim 1, wherein symmetrizing the coefficient matrix includes preserving diagonal elements of the coefficient matrix.

### Claim 8 (depends on 1)

The apparatus of claim 1, wherein multiplying the coefficient matrix by the left and right scale-factor preconditioning matrices includes utilizing the left and right scale-factor preconditioning matrices Pl and Pr, in which:
P
l
=
[
⋱
s
y
j

s
z
k
s
z
k

s
x
i
s
x
i

s
y
j
⋱
]
P
r
=
[
⋱
1

/

s
x
i
+
1

/

2
1

/

s
y
j
+
1

/

2
1

/

s
z
k
+
1

/

2
⋱
]
.

### Claim 9 (depends on 1)

The apparatus of claim 1, wherein symmetrizing the coefficient matrix includes utilizing left and the right diagonally-dominant preconditioning matrices Pl and Pr, in which:

P
l
=
[
⋱
1
?

?

?
1
?

?

?
1
?

?

?
⋱
]

P
r
=
[
⋱
?

?

?
?

?

?
?

?

?
⋱
]
.

?

indicates text missing or illegible when filed

### Claim 10 (depends on 1)

The apparatus of claim 1, wherein confining a majority of eigenvalues of the coefficient matrix includes shifting eigenvalues, which are outside the half-plane, into the half-plane by modifying the coefficient matrix.

### Claim 11 (depends on 10)

The apparatus of claim 10, wherein shifting eigenvalues includes one of:
shifting the eigenvalues so that at least 75% of the eigenvalues are in the half-plane,
shifting the eigenvalues so that at least 90% of the eigenvalues are in the half-plane, and
shifting the eigenvalues so that at least 95% of the eigenvalues are in the half-plane.

### Claim 12

A method for simulating a physical phenomenon characterized by a set of partial differential equations that are reduced based on harmonic time dependence, the method comprising:
in a data computing circuit having stored therefor a system of linear equations representing an operation in the differential equations and in which a coefficient matrix is multiplied by an unknown column vector and with the product thereof being equal to a column vector, solving the system of linear equations by executing an algorithm that sets forth at least one of the following three sets of operations:
multiplying the coefficient matrix by left and right scale-factor preconditioning matrices, and multiplying the column vector b by the left scale-factor preconditioning matrix, each matrix including at least one of: entries of scale factors and combinations of scale factors of a perfectly matched layer,
symmetrizing the coefficient matrix by multiplying the coefficient matrix by left and right diagonally-dominant preconditioning matrices while maintaining a condition number of the coefficient matrix within an order of magnitude of a condition number of the matrix prior to symmetrizing, and
confining a majority of eigenvalues of the coefficient matrix in a half-plane having a boundary that crosses an origin of a complex plane.

### Claim 13 (depends on 12)

The method of claim 12, further including, in the data computing circuit,
receiving data characterizing the physical phenomenon, and
executing the algorithm, using the received data as an input, to solve the system of linear equations and generate an output that characterizes the physical phenomenon.

### Claim 14 (depends on 13)

The method of claim 13, wherein executing the algorithm includes at least one of:
executing the algorithm with received electromagnetic wave data to solve the linear equations and generate an output that characterizes the behavior of the electromagnetic wave;
executing the algorithm with received optical wave data to solve the linear equations and generate an output that characterizes behavior of the optical wave;
executing the algorithm with received fluid dynamics system data to solve the linear equations and generate an output that characterizes behavior of the fluid dynamics system;
executing the algorithm with received chemical reaction data to solve the linear equations and generate an output that characterizes behavior of the chemical reaction; and
executing the algorithm with received mechanical system data to solve the linear equations and generate an output that characterizes behavior of the mechanical system.

### Claim 15 (depends on 12)

The method of claim 12, wherein solving the system of linear equations includes performing at least two of the operations.

### Claim 16 (depends on 12)

The method of claim 12, wherein solving the system of linear equations includes performing all of the operations.

### Claim 17 (depends on 12)

The method of claim 12, wherein executing the algorithm includes executing an algorithm that sets forth the operation of confining the majority of eigenvalues of the coefficient matrix in the half-plane, and thereafter, performing at least one of the operations of multiplying the coefficient matrix by the left and right scale-factor preconditioning matrices and symmetrizing the coefficient matrix.

### Claim 18 (depends on 12)

The method of claim 12, wherein symmetrizing the coefficient matrix includes preserving diagonal elements of the coefficient matrix.

### Claim 19 (depends on 12)

The method of claim 12, wherein multiplying the coefficient matrix by the left and right scale-factor preconditioning matrices includes utilizing the left and right scale-factor preconditioning matrices Pl and Pr, in which:
P
l
=
[
⋱
s
y
j

s
z
k
s
z
k

s
x
i
s
x
i

s
y
j
⋱
]
P
r
=
[
⋱
1

/

s
x
i
+
1

/

2
1

/

s
y
j
+
1

/

2
1

/

s
z
k
+
1

/

2
⋱
]
.

### Claim 20 (depends on 12)

The method of claim 12, wherein symmetrizing the coefficient matrix includes utilizing left and the right diagonally-dominant preconditioning matrices Pl and Pr, in which:

P
l
=
[
⋱
1
?

?

?
1
?

?

?
1
?

?

?
⋱
]

P
r
=
[
⋱
?

?

?
?

?

?
?

?

?
⋱
]
.

?

indicates text missing or illegible when filed

### Claim 21 (depends on 12)

The method of claim 12, wherein confining a majority of eigenvalues of the coefficient matrix includes shifting eigenvalues, which are outside the half-plane, into the half-plane by modifying the coefficient matrix.

### Claim 22 (depends on 21)

The method of claim 21, wherein shifting eigenvalues includes one of:
shifting the eigenvalues so that at least 75% of the eigenvalues are in the half-plane,
shifting the eigenvalues so that at least 90% of the eigenvalues are in the half-plane, and
shifting the eigenvalues so that at least 95% of the eigenvalues are in the half-plane.

### Claim 23

An article of manufacture for simulating a physical phenomenon characterized by a set of partial differential equations that are reduced based on harmonic time dependence, comprising:
for execution by a processor having stored therefor a system of linear equations representing an operation in the differential equations and in which a coefficient matrix is multiplied by an unknown column vector and with the product thereof being equal to a column vector, a non-transitory processor-readable storage medium configured and arranged with program data that, when executed by the processor, causes the processor to solve the system of linear equations by at least one of:
multiplying the coefficient matrix by left and right scale-factor preconditioning matrices, and multiplying the column vector b by the left scale-factor preconditioning matrix, each matrix including entries of scale factors or combinations of scale factors of a perfectly matched layer,
symmetrizing the coefficient matrix by multiplying the coefficient matrix by left and right diagonally-dominant preconditioning matrices while maintaining a condition number of the coefficient matrix within an order of magnitude of a condition number of the matrix prior to symmetrizing, and
confining a majority of eigenvalues of the coefficient matrix in a half-plane having a boundary that crosses an origin of a complex plane.

### Claim 24 (depends on 23)

The article of manufacture of claim 23, wherein the processor is configured and arranged to execute the algorithm to solve the linear equations by at least one of:
executing the algorithm with received electromagnetic wave data to solve the linear equations and generate an output that characterizes the behavior of the electromagnetic wave;
executing the algorithm with received optical wave data to solve the linear equations and generate an output that characterizes behavior of the optical wave;
executing the algorithm with received fluid dynamics system data to solve the linear equations and generate an output that characterizes behavior of the fluid dynamics system;
executing the algorithm with received chemical reaction data to solve the linear equations and generate an output that characterizes behavior of the chemical reaction; and
executing the algorithm with received mechanical system data to solve the linear equations and generate an output that characterizes behavior of the mechanical system.
