# US 2013/0279293 A1 · Vectorization of fast fourier transform for elastic wave propogation for use in seismic underwater exploration of geographical areas of interest

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

- Number: US 2013/0279293 A1
- Document ID: US20130279293A1
- Status: Published application
- Kind: A1
- Application number: 13/865,614
- Filed: 2013-04-18
- Published: 2013-10-24
- Earliest claimed: 2012-04-19
- Assignees: Cggveritas Services SA
- Applicants: Cggveritas Services SA
- Inventors: Sheng XU; Feng CHEN
- Web page: https://patentgrep.com/patent/US20130279293A1

## CPC

- G01V 1/282: {Application of seismic models, synthetic seismograms}
- G01V 1/28: Processing seismic data, e.g. for interpretation or for event detection (G01V1/48 takes precedence)
- G01V 2210/67: Wave propagation modeling
- G01V 2210/675: Wave equation; Green's functions
- G01V: GEOPHYSICS; GRAVITATIONAL MEASUREMENTS; DETECTING MASSES OR OBJECTS; TAGS (means for indicating the location of accidentally buried, e.g. snow-buried, persons A63B29/02)

## Abstract

Numerical simulations of elastic wave propagation algorithms are critical components for seismic imaging and inversion. Finite-difference schemes yield good efficiency but cannot ensure the accuracy of the high frequency component. Pseudo-spectral algorithms are accurate up to the Nyquist frequency, but its efficiency depends on the optimization of the fast Fourier transform (FFT) algorithm. The conventional FFT algorithms are optimized for signal processing, in which problems are generally one dimensional time series. For 3D wave propagation, FFT algorithms have the potential to be further optimized. Under current computer hardware architecture, a vectorization scheme for high dimensional FFTs is presented. Compared to conventional numerical scheme implementations, the systems and methods disclose herein has the best performance on the slowest or higher dimensions of data. For elastic wave propagation, vectorization improves the efficiency by more than a factor of two when compared to standard FFT algorithms.

## Claims

### Claim 1

A method for simulating and displaying wave propagation using reflection seismology in a geographical area of interest, the method comprising:
converting signals associated with marine seismic soundwaves into digital electronic form, and storing the same as single precision floating numbers in an array of size N;
converting the real array of size N into a complex array of size N/2;
determining a first derivative of the following elastic wave equation—
ρ

(
x
)

∂
2

u
i
∂
t
2
-
∂
∂
x
j

C
ijkl

∂
∂
x
l

u
k
=
f
i
using the following equation—
Z
k
′
=


(
N
4
+
N
4

sin

2

π


k
N
-
k
)

Z
k
+
N
4

cos

2

π


k
N

Z
k
†
*
wherein said determination of the first derivative includes the determination of a fast fourier transform using an FFT vectorization scheme;
using the calculated derivatives of the elastic wave equation to determine wavefield propagation underground; and
processing the calculated derivatives into data that can be used to display the determined wavefields so that underground geographical features in the underground geographical area of interest can be determined.

### Claim 2 (depends on 1)

The method according to claim 1, wherein the step of determining a first derivative of the elastic wave equation comprises:
combining sequential pairs of even and odd real numbers of the N-sized real array to form a plurality of sequential complex numbers according to the following equation
zn=x2n+ix2n+1=xn(e)+ixn(o),
in which n=0, . . . ,
N
2
-
1
;
performing an FFT calculation of zn to obtain Zk using the FFT vectorization scheme, and then determining the complex conjugate and conjugate transpose of Zk, Zk†*;
using the following relationships to determine the first derivative, Zk′, of the elastic wave equation by
defining the frequency representation of xn(e) and xn(o) as—
X
k
(
e
)
=
1
2

(
Z
k
+
Z
k
†
*
)


and


X
k
(
o
)
=
-

2

(
Z
k
-
Z
k
†
*
)
where k=0, . . . ,
N
2
-
1
,
k
†
=
N
2
-
k
and Zk is the FFT of zn;
splitting the FFT of zn into a size-N real array of even and odd terms according to the following—
X
k
=
∑
n
=
0
N
2
-
1


x
n
(
e
)


-


2

π


kn
N
/
2
+

-


2

π


k
N

∑
n
=
0
N
2
-
1


x
n
(
o
)


-


2

π


kn
N
/
2
=
X
k
(
e
)
+

-


2

π


k
N
,

and


therefore


X
k
=
1
2

[
(
Z
k
+
Z
k
†
*
)
-

-


2

π


k
N

(
Z
k
-
Z
k
†
*
)
]
,
(
6
)
where k=0, . . . ,
N
2
-
1
and can be extended to
k
=
N
2
by defining
Z
N
2
=
Z
o
,
and
X
k
†
=
1
2

[
(
Z
k
+
Z
k
†
*
)
+

-


2

π


k
N

(
Z
k
-
Z
k
†
*
)
]
*
;
and
having determined Zk and Zk†*, determining the derivative of the elastic wave equation, Zk′, according to the following—
Z
k
′
=


(
N
4
+
N
4

sin

2

π


k
N
-
k
)

Z
k
+
N
4

cos

2

π


k
N

Z
k
†
*
.

### Claim 3 (depends on 1)

The method according to claim 1, wherein the step of determining a fast Fourier transform using an FFT vectorization scheme comprises:
storing a first set of data in memory, such that the data is configured in a first array of N rows, and M columns;
reconfiguring the first array such that it is now comprises of N vectors each of length M, without moving any data of the first array;
calculating an FFT of the data stored in the first array configured as N vectors each of length M using a vectorization scheme; and
returning the FFT result.

### Claim 4 (depends on 3)

The method according to claim 3, wherein the vectorization scheme is a streaming, single instruction, multiple data (SIMD) extension (SSE) scheme.

### Claim 5 (depends on 4)

The method according to claim 4, wherein the SSE is used to multiple a twiddle factor in the determination of the FFT.

### Claim 6 (depends on 3)

The method according to claim 3, wherein the step of storing the data includes storing data in a three dimensional (3D) format, and further wherein the step of reconfiguring the first array includes determining that the set of vectors also includes Z sets of vectors, wherein each the Z sets of vectors includes N vectors of length M.

### Claim 7 (depends on 1)

The method according to claim 1, wherein the steps of storing and determining first derivatives of the elastic wave equation comprise:
storing three dimensional data in a three dimensional format; and
determining the first derivatives in each of the three dimensions using an FFT vectorization scheme in a parallel manner, at substantially the same time.

### Claim 8

A method for simulating and displaying wave propagation using reflection seismology in a geographical area of interest, the method comprising:
transmitting a plurality of marine seismic sound waves by a plurality of transmitters;
receiving one or more of the plurality of transmitted signals by a plurality of receivers;
converting the received signals into digital electronic form, and storing the same as single precision floating numbers in an array of size N;
converting the real array of size N into a complex array of size N/2;
determining a first derivative of the following elastic wave equation—
ρ

(
x
)

∂
2

u
i
∂
t
2
-
∂
∂
x
j

C
ijkl

∂
∂
x
l

u
k
=
f
i
using the following equation—
Z
k
′
=
i

(
N
4
+
N
4

sin

2


π


k
N
-
k
)

Z
k
+
N
4

cos

2

π


k
N

Z
k
†
*
wherein said determination of the first derivative includes the determination of a fast Fourier transform using an FFT vectorization scheme;
using the calculated derivatives of the elastic wave equation to determine wavefield propagation underground; and
processing the calculated derivatives to visually display the determined wavefields so that underground geographical features in the underground geographical area of interest can be visually displayed and determined.

### Claim 9

A system for simulating and displaying wave propagation using reflection seismology in a geographical area of interest, the system comprising:
a processor configured to convert signals associated with marine seismic soundwaves into digital electronic form, and storing the same as single precision floating numbers in an array of size N, and wherein the processor is further configured to
convert the real array of size N into a complex array of size N/2;
determine a first derivative of the following elastic wave equation—
ρ

(
x
)

∂
2

u
i
∂
t
2
-
∂
∂
x
j

C
ijkl

∂
∂
x
l

u
k
=
f
i
using the following equation—
Z
k
′
=


(
N
4
+
N
4

sin

2


π


k
N
-
k
)

Z
k
+
N
4

cos

2

π


k
N

Z
k
†
*
wherein said determination of the first derivative includes the determination of a fast Fourier transform using an FFT vectorization scheme, and further wherein the processor is further configured to
use the calculated derivatives of the elastic wave equation to determine wavefield propagation underground, and
process the calculated derivatives into data that can be used to display the determined wavefields so that underground geographical features in the underground geographical area of interest can be determined.

### Claim 10 (depends on 9)

The system according to claim 9, wherein the determining a first derivative of the elastic wave equation by the processor comprises:
the processor being further configured to
combine sequential pairs of even and odd real numbers of the N-sized real array to form a plurality of sequential complex numbers according to the following equation
zn=x2n+ix2n+1=xn(e)+ixn(o),
in which n=0, . . . ,
N
2
-
1
;
perform an FFT calculation of zn to obtain Zk using the FFT vectorization scheme,
determine the complex conjugate and conjugate transpose of Zk, Zk†*,
use the following relationships to determine the first derivative, Zk′, of the elastic wave equation by defining the frequency representation of xn(e) and xn(o) as—
X
k
(
e
)
=
1
2

(
Z
k
+
Z
k
†
*
)


and


X
k
(
o
)
=
-

2

(
Z
k
-
Z
k
†
*
)
where k=0, . . .
N
2
-
1
,
k
†
=
N
2
-
k
and Zk is the FFT of zn,
split the FFT of zn into a size-N real array of even and odd terms according to the following—
X
k
=
∑
n
=
0
N
2
-
1

x
n
(
e
)


-


2

π


kn
N
/
2
+

-


2

π


k
N

∑
n
=
0
N
2
-
1

x
n
(
o
)


-


2

π


kn
N
/
2
=
X
k
(
e
)
+

-


2

π


k
N
,

and


therefore


X
k
=
1
2

[
(
Z
k
+
Z
k
†
*
)
-




-


2

π


k
N

(
Z
k
-
Z
k
†
*
)
]
,
(
6
)
where k=0, . . . ,
N
2
-
1
and can be extended to
k
=
N
2
by defining
Z
N
2
=
Z
0
,
and
X
k
†
=
1
2

[
(
Z
k
+
Z
k
†
*
)
+




-


2

π


k
N

(
Z
k
-
Z
k
†
*
)
]
*
;
and
having determined Zk and Zk†*, the processor is further configured to
determine the derivative of the elastic wave equation, Zk′, according to the following—
Z
k
′
=


(
N
4
+
N
4

sin

2


π


k
N
-
k
)

Z
k
+
N
4

cos

2

π


k
N

Z
k
†
*
.

### Claim 11 (depends on 9)

The system according to claim 9, wherein determining a fast Fourier transform using an FFT vectorization scheme by the processor comprises:
the processor being further configured to
store a first set of data in memory, such that the data is configured in a first array of N rows, and M columns;
reconfigure the first array such that it is now comprises of N vectors each of length M, without moving any data of the first array;
calculate an FFT of the data stored in the first array configured as N vectors each of length M using a vectorization scheme; and
return the FFT result.

### Claim 12 (depends on 11)

The system according to claim 11, wherein the vectorization scheme is a streaming, single instruction, multiple data (SIMD) extension (SSE) scheme.

### Claim 13 (depends on 12)

The system according to claim 12, wherein the SSE is used to multiple a twiddle factor in the determination of the FFT.

### Claim 14 (depends on 11)

The system according to claim 11, wherein storing the data includes storing data by the processor in a three dimensional (3D) format, and further wherein reconfiguring the first array by the processor includes determining that the set of vectors also includes Z sets of vectors, wherein each the Z sets of vectors includes N vectors of length M.

### Claim 15 (depends on 9)

The system according to claim 9, wherein storing and determining first derivatives of the elastic wave equation by the processor comprises:
the processor being further configured to
store three dimensional data in a three dimensional format; and
determine the first derivatives in each of the three dimensions using an FFT vectorization scheme in a parallel manner, at substantially the same time.

### Claim 16

A system for simulating and displaying wave propagation using reflection seismology in a geographical area of interest, the system comprising:
a plurality of transmitters configured to transmit a plurality of marine seismic sound waves;
a plurality of receiver configured to receive one or more of the plurality of transmitted signals; and
a processor configured to
convert the received signals into digital electronic form, and storing the same as single precision floating numbers in an array of size N;
convert the real array of size N into a complex array of size N/2;
determine a first derivative of the following elastic wave equation—
ρ

(
x
)

∂
2

u
i
∂
t
2
-
∂
∂
x
j

C
ijkl

∂
∂
x
l

u
k
=
f
i
using the following equation—
Z
k
′
=


(
N
4
+
N
4

sin

2


π


k
N
-
k
)

Z
k
+
N
4

cos

2

π


k
N

Z
k
†
*
wherein said determination of the first derivative includes the determination of a fast Fourier transform using an FFT vectorization scheme;
use the calculated derivatives of the elastic wave equation to determine wavefield propagation underground; and
process the calculated derivatives to visually display the determined wavefields so that underground geographical features in the underground geographical area of interest can be visually displayed and determined.
