:: wikimiki.org ::

Discrete Fourier Transform

Discrete Fourier transform

In mathematics, the discrete Fourier transform (DFT), sometimes called the finite Fourier transform, is a Fourier transform widely employed in signal processing and related fields to analyze the frequencies contained in a sampled signal, solve partial differential equations, and to perform other operations such as convolutions. The DFT can be computed efficiently in practice using a fast Fourier transform (FFT) algorithm. The sequence of n complex numbers x₀, ..., x_n−1 are transformed into the sequence of n complex numbers f₀, ..., f_n−1 by the DFT according to the formula: :

f_j = \sum_^ x_k e^ \quad \quad j = 0, \dots, n-1

where e is the base of the natural logarithm, i is the imaginary unit (

i^2=-1

), and π is Pi. The transform is sometimes denoted by the symbol

\mathcal

, as in

\mathbf = \mathcal(\mathbf)

\mathcal \mathbf

. The inverse discrete Fourier transform (IDFT) is given by :

x_k = \frac \sum_^ f_j e^ \quad \quad k = 0,\dots,n-1.

Note that the normalization factor multiplying the DFT and IDFT (here 1 and 1/n) and the signs of the exponents are merely conventions, and differ in some treatments. The only requirements of these conventions are that the DFT and IDFT have opposite-sign exponents and that the product of their normalization factors be 1/n. A normalization of

1/\sqrt

for both the DFT and IDFT makes the transforms unitary, which has some theoretical advantages, but it is often more practical in numerical computation to perform the scaling all at once as above (and a unit scaling can be convenient in other ways). (The convention of a negative sign in the exponent is often convenient because it means that

f_j

is the amplitude of a "positive frequency"

2\pi j/n

. Equivalently, the DFT is often thought of as a matched filter: when looking for a frequency of +1, one correlates the incoming signal with a frequency of −1.) In the following discussion the terms "sequence" and "vector" will be considered interchangeable.

Properties

Completeness

The discrete Fourier transform is an invertible, linear transformation :

\mathcal:\mathbf^n \to \mathbf^n

with C denoting the set of complex numbers. In other words, for any n ≥ 0, any n-dimensional complex vector has a DFT and an IDFT which are in turn n-dimensional complex vectors.

Orthogonality

The vectors exp(2πi jk/n) form an orthogonal basis over the set of n-dimensional complex vectors: :

\sum_^
\left(e^\right)
\left(e^\right)
=n~\delta_

where δ_jk is the Kronecker delta.

The Plancherel theorem and Parseval's theorem

If X_j and Y_j are the DFTs of x_k and y_k respectively then we have the Plancherel theorem: :

\sum_^ x_k y^ - _k = \frac \sum_^ X_j Y^ - _j

where the star denotes complex conjugation. Parseval's theorem is a special case of the Plancherel theorem and states: :

\sum_^ |x_k|^2 = \frac \sum_^ |X_j|^2.

The shift theorem

Multiplying

x_k

by a linear phase

\exp(2\pi i k m/n)

for some integer

m

corresponds to a circular shift of the output

f_j

f_j

is replaced by

f_

, where the subscript is interpreted modulo

n

(i.e. periodically). Similarly, a circular shift of the input

x_k

corresponds to multiplying the output

f_j

by a linear phase. Mathematically, if

\

represents the vector x then :if

\mathcal(\)_j=f_j

:then

\mathcal(\)_j=f_

:and

\mathcal(\)_j=f_j e^

Periodicity and aliasing

Although the DFT transforms n numbers to n numbers, in many ways it can be thought of as implicitly operating on infinite periodic sequences of both inputs and outputs. (Indeed, the DFT can be derived as the continuous Fourier transform of infinite periodic sequences of impulses.) If one simply evaluates the DFT formula at

j + n

then one finds that

f_ = f_j

, because

\exp[-2\pi i (j+n) k / n]

is equal to

\exp[-2\pi i j k / n] \exp[-2\pi i n k / n]

which equals

\exp[-2\pi i j k / n]

. This phenomenon is called aliasing, and it means that in a discrete signal one cannot distinguish between frequencies

j

that differ by

n

. For the same reason, if one evaluates the inverse DFT formula at

k + n

then one finds that

x_ = x_k

. Thus, the inputs also have implicitly periodic boundaries. The shift theorem, above, is also an expression of this implicit periodicity, because it shows that the DFT amplitudes

|f_j|

are unaffected by a circular (periodic) shift of the inputs, which is simply a choice of origin and therefore only affects the phase. These periodic boundary conditions play an important role in many applications of the DFT. When solving differential equations they allow periodic boundary conditions to be automatically satisfied, and thus can be a useful property. For digital signal processing on the other hand, the periodicity is usually an obstacle—not only does it alias high frequencies with low frequencies, as noted above, but it also tends to introduce artifacts because natural signals are often non-periodic (resulting in implied discontinuities between the ends of the input). See also the applications section below.

Circular convolution theorem and cross-correlation theorem

The cyclic convolution x
- y of the two vectors x = x_j and y = y_k is the vector x
- y with components :

(\mathbf)_k = \sum_^ x_j y_ \quad \quad k = 0,\dots,n-1

where we continue y cyclically so that :

y_ = y_\quad\quad~~~~~~~~~~ j = 0, ..., n-1

The discrete Fourier transform turns cyclic convolutions into component-wise multiplication. That is, if

z_k = (\mathbf)_k

then :

Z_j=X_j Y_j \quad \quad~~~~~~~~~~ j = 0,\dots,n-1

where capital letters (X, Y, Z) represent the DFTs of sequences represented by small letters (x, y, z). Note that if a different normalization convention is adopted for the DFT (e.g., the unitary normalization), then there will in general be a constant factor multiplying the above relation. The direct evaluation of the convolution summation, above, would require

O(n^2)

operations, but the DFT (via an FFT) provides an

O(n\log n)

method to compute the same thing. Conversely, convolutions can be used to efficiently compute DFTs via Rader's FFT algorithm and Bluestein's FFT algorithm. See also: Convolution theorem In an analogous manner, it can be shown that if

z_k

is the cross-correlation of

x_j

and

y_j

: :

z_k=(\mathbf)_k = \sum_^x_j^ - \,y_

where the sum is again cyclic in j, then the discrete Fourier transform of

z_k

is: :

Z_k = X_k^ - \,Y_k

where capital letters are again used to signify the discrete Fourier transform.

Relationship to trigonometric interpolation polynomials

The function :

p(t) = \frac + \frac e^ + \frac e^ + \cdots + \frac e^

whose coefficients f_j /n are given by the DFT of x_k, above, is called the trigonometric interpolation polynomial of degree n − 1. It is the unique function of this form that satisfies the property: p(2πk/n) = x_k for k = 0, ..., n − 1. Because of aliasing, however, the form of the trigonometric interpolation polynomial is not unique, in that any of the frequencies can be shifted by any multiple of n while maintaining the property p(2πk/n) = x_k . In particular, the following form is often preferred: :

p(t) = \frac + \frac e^ + \cdots + \frac \cos(nt/2) + \frac e^ + \cdots + \frac e^

for even

n

(where the Nyquist amplitude

f_

should be handled specially) or, for odd

n

: :

p(t) = \frac + \frac e^ + \cdots + \frac e^ + \frac e^ + \cdots + \frac e^

These latter two forms have the useful property that, if the

x_k

are all real numbers, then

p(t)

will be real for all

t

as well. They also use the smallest possible frequencies of the interpolating sinusoids (a balance of positive and negative frequencies instead of all positive frequencies), and consequently minimize the mean-square slope

\int |p'(t)|^2 dt

of the interpolated function.

The unitary DFT

Another way of looking at the DFT is to note that in the above discussion, the DFT can be expressed as a Vandermonde matrix: :

\mathbf =
\begin
 \omega_n^     & \omega_n^     & \ldots & \omega_n^     \\
 \omega_n^     & \omega_n^     & \ldots & \omega_n^     \\
 \vdots                   & \vdots                   & \ddots & \vdots                       \\
 \omega_n^ & \omega_n^ & \ldots & \omega_n^ \\
\end

where :

\omega_n = e^\,

is a primitive nth root of unity. The inverse transform is then given by the inverse of the above matrix: :

\mathbf^=\frac\mathbf^ -

With unitary normalization constants

1/\sqrt

, the DFT becomes a unitary transformation, defined by a unitary matrix: :

\mathbf=\mathbf/\sqrt

\mathbf^=\mathbf^ -

\det(\mathbf)=1

where det() is the determinant function. In a real vector space, a unitary transformation can be thought of as simply a rigid rotation of the coordinate system, and all of the properties of a rigid rotation can be found in the unitary DFT. The orthogonality of the DFT is now expressed as an orthonormality condition (which arises in many areas of mathematics as described in root of unity): :

\sum_^U_U_^ - =\delta_

\mathbf

is defined as the unitary DFT of the vector

\mathbf

then :

X_j=\sum_^ U_x_k

and the Plancherel theorem is expressed as: :

\sum_^x_k y_k^ -  = \sum_^X_j Y_j^ -

If we view the DFT as just a coordinate transformation which simply specifies the components of a vector in a new coordinate system, then the above is just the statement that the dot product of two vectors is preserved under a unitary DFT transformation. For the special case

\mathbf = \mathbf

, this implies that the length of a vector is preserved as well—this is just Parseval's theorem: :

\sum_^|x_k|^2 = \sum_^|X_j|^2

Expressing the inverse DFT in terms of the DFT

A useful property of the DFT is that the inverse DFT can be easily expressed in terms of the (forward) DFT, via several well-known "tricks". (For example, in computations, it is often convenient to only implement a fast Fourier transform corresponding to one transform direction and then to get the other transform direction from the first.) First, we can compute the inverse DFT by reversing the inputs: :

\mathcal^(\) = \mathcal(\) / n

(As usual, the subscripts are interpreted modulo

n

; thus, for

k=0

, we have

x_=x_0

.) Second, one can also conjugate the inputs and outputs: :

\mathcal^(\mathbf) = \mathcal(\mathbf^ - )^ -  / n

Third, a variant of this conjugation trick, which is sometimes preferable because it requires no modification of the data values, involves swapping real and imaginary parts (which can be done on a computer simply by modifying pointers). Define swap(

x_k

) as

x_k

with its real and imaginary parts swapped—that is, if

x_k = a + b i

then swap(

x_k

) is

b + a i

. Equivalently, swap(

x_k

) equals

i x_k^ -

. Then :

\mathcal^(\mathbf) = \textrm(\mathcal(\textrm(\mathbf))) / n

That is, the inverse transform is the same as the forward transform with the real and imaginary parts swapped for both input and output, up to a normalization The conjugation trick can also be used to define a new transform, closely related to the DFT, that is involutary—that is, which is its own inverse. In particular,

T(\mathbf) = \mathcal(\mathbf^ - ) / \sqrt

is clearly its own inverse:

T(T(\mathbf)) = \mathbf

. A closely related involutary transformation (by a factor of (1+i)/√2) is

H(\mathbf) = \mathcal((1+i) \mathbf^ - ) / \sqrt

, since the

(1+i)

factors in

H(H(\mathbf))

cancel the 2. For real inputs

\mathbf

, the real part of

H(\mathbf)

is none other than the discrete Hartley transform, which is also involutary.

The real DFT

x_0, \ldots, x_

are real numbers, as they often are in practical applications, then the DFT obeys the symmetry: :

f_j = f_^ -  ,

where the star denotes complex conjugation and the subscripts are interpreted modulo n. Therefore, the DFT output for real inputs is half redundant, and one obtains the complete information by only looking at roughly half of the outputs

f_0, \ldots, f_

. In this case, the "DC" element

f_0

is purely real, and for even n the "Nyquist" element

f_

is also real, so there are exactly n non-redundant real numbers in the first half + Nyquist element of the complex output f. Using Euler's formula, the interpolating trigonometric polynomial can then be interpreted as a sum of sine and cosine functions.

Generalized DFT

It is possible to shift the transform sampling in time and/or frequency domain by some real shifts a and b, respectively. This is sometimes known as a generalized DFT (or GDFT) and has analogous properties to the ordinary DFT: :

f_j = \sum_^ x_k e^ \quad \quad j = 0, \dots, n-1

Most often, shifts of

1/2

(half a sample) are used. While the ordinary DFT corresponds to a periodic signal in both time and frequency domains,

a=1/2

produces a signal that is anti-periodic in frequency domain (

f_ = - f_j

) and vice-versa for

b=1/2

. Thus, the specific case of

a = b = 1/2

is known as an odd-time odd-frequency discrete Fourier transform (or O² DFT). Such shifted transforms are most often used for symmetric data, to represent different boundary symmetries, and for real-symmetric data they correspond to different forms of the discrete cosine and sine transforms. The discrete Fourier transform can be viewed as a special case of the z-transform, evaluated on the unit circle in the complex plane.

Multidimensional DFT

The ordinary DFT computes the transform of a "one-dimensional" dataset: an sequence (or array)

x_k

that is a function of one discrete variable

k

. More generally, one can define the multidimensional DFT of a multidimensional array

x_

that is a function of

d

discrete variables

k_\ell = 0, 1, \cdots, n_\ell-1

for

\ell

1, 2, \cdots, d

: :

f_ = \sum_^ \omega_^ \cdots \sum_^ \omega_^ x_ \, ,

where

\omega_ = \exp(-2\pi i/n_\ell)

as above and the

d

output indices run from

j_\ell = 0, 1, \cdots, n_\ell-1

. This is more compactly expressed in vector notation, where

\mathbf \equiv (k_1, k_2, \cdots, k_d)

and

\mathbf \equiv (j_1, j_2, \cdots, j_d)

are

d

-dimensional vectors of indices from 0 to

\mathbf - 1 \equiv (n_1 - 1, n_2 - 1, \cdots, n_d - 1)

: :

f_\mathbf = \sum_^ e^ x_\mathbf \, ,

where the division

\mathbf / \mathbf \equiv (k_1/n_1, \cdots, k_d/n_d)

is performed element-wise, and the sum denotes the set of nested summations above. The inverse of the multi-dimensional DFT is, analogous to the one-dimensional case, given by: :

x_\mathbf = \frac \sum_^ e^ f_\mathbf \, .

The multidimensional DFT has a simple interpretation. Just as the one-dimensional DFT expresses the input

x_k

as a superposition of sinusoids, the multidimensional DFT expresses the input as a superposition of plane waves, or sinusoids oscillating along the direction

\mathbf / \mathbf

in space and having amplitude

f_\mathbf

. Such a decomposition is of great importance for everything from digital image processing (

d

=2) to solving partial differential equations in three dimensions (

d

=3) by breaking the solution up into plane waves. Computationally, the multidimensional DFT is simply the composition of a sequence of one-dimensional DFTs along each dimension. For example, in the two-dimensional case

x_

one can first compute the

n_1

independent DFTs of the rows (i.e., along

k_2

) to form a new array

y_

, and then compute the

n_2

independent DFTs of

y

along the columns (along

k_1

) to form the final result

f_

. Or, one can transform the columns and then the rows—the order is immaterial because the nested summations above commute. Because of this, given a way to compute a one-dimensional DFT (e.g. an ordinary one-dimensional FFT algorithm), one immediately has a way to efficiently compute the multidimensional DFT. This is known as a row-column algorithm, although there are also intrinsically multi-dimensional FFT algorithms.

Applications

The DFT has seen wide usage across a large number of fields; we only sketch a few examples below (see also the references at the end). All applications of the DFT depend crucially on the availability of a fast algorithm to compute discrete Fourier transforms and their inverses, a fast Fourier transform.

Spectral analysis

Suppose a signal x(t) is to be analyzed. Here, t stands for time, which varies over the interval [0,T], and, in the case of a sound signal, x(t) is the air pressure at time t. The signal is sampled at n equidistant points to get the n real numbers x₀ = x(0), x₁ = x(h), x₂ = x(2h), ..., x_n−1 = x((n−1)h), where h = T/n and n is even. Then the discrete Fourier transform f₀, ..., f_n−1 is computed and the numbers f_{n/2 + 1}, ..., f_n−1 are discarded (they are redundant for real signals). Then f₀/n approximates the average value of the signal over the interval, and for every j = 1, ..., n/2, the argument (see complex number) arg(f_j) represents the phase and the modulus |f_j|/n represents one half of the amplitude of the component of the signal having frequency j/T (see wave). The reason behind this interpretation is that the f_j are approximations to the coefficients occurring in the Fourier series expansion of x(t). Or, more commonly, T is a small section of an infinite signal x(t), and the DFT is an approximation for the discrete-time Fourier transform of the sampled signal, which in turn is an approximation for the continuous Fourier transform if x(t) is band-limited (see the Nyquist frequency). In general, the problem of using the DFT of discrete samples to approximate the Fourier transform of an infinite, continuous signal is called spectral estimation, and involves many more details than are described here. For an example see frequency spectrum.

Data compression

The field of digital signal processing relies heavily on operations in the frequency domain (i.e. on the Fourier transform). For example, several lossy image and sound compression methods employ the discrete Fourier transform: the signal is cut into short segments, each is transformed, and then the Fourier coefficients of high frequencies, which are assumed to be unnoticeable, are discarded. The decompressor computes the inverse transform based on this reduced number of Fourier coefficients. (Compression applications often use a specialized form of the DFT, the discrete cosine transform or sometimes the modified discrete cosine transform).

Partial differential equations

Discrete Fourier transforms, especially in more than one dimension, are often used to solve partial differential equations, where again the DFT is used as an approximation for the Fourier series (which is recovered in the limit of infinite n). The reason is that it expands the signal in complex exponentials e^ikx, which are eigenfunctions of differentiation: d/dx e^ikx = ik e^ikx. Thus, in the Fourier representation, a linear differential equation with constant coefficients is transformed into an easily solvable algebraic equation. One then uses the inverse DFT to transform the result back into the ordinary spatial representation. Such an approach is called a spectral method.

Multiplication of large integers

The fastest known algorithms for the multiplication of large integers or polynomials are based on the discrete Fourier transform: the sequences of digits or coefficients are interpreted as vectors whose convolution needs to be computed; in order to do this, they are first Fourier-transformed, then multiplied component-wise, then transformed back.

Outline of DFT polynomial multiplication algorithm

Suppose we wish to compute the polynomial product c(x) = a(x) · b(x). The ordinary product expression for the coefficients of c involves a linear (acyclic) convolution, where indices do not "wrap around." This can be rewritten as a cyclic convolution by taking the coefficient vectors for a(x) and b(x) with constant term first, then appending zeros so that the resultant coefficient vectors a and b have dimension d > deg(a(x)) + deg(b(x)). Then, :

\mathbf = \mathbf \star \mathbf

Where c is the vector of coefficients for c(x), and the convolution operator

\star

is defined so :

c_i = \sum_^a_j b_ \qquad\qquad\qquad i=0,1,...,d-1

But convolution becomes multiplication under the DFT: :

\mathcal(\mathbf) = \mathcal(\mathbf)\mathcal(\mathbf)

Here the vector product is taken elementwise. Thus the coefficients of the product polynomial c(x) are just the terms 0, ..., deg(a(x)) + deg(b(x)) of the coefficient vector :

\mathbf = \mathcal^(\mathcal(\mathbf)\mathcal(\mathbf))

With a Fast Fourier transform, the resulting algorithm takes O(n log n) arithmetic operations. Due to its simplicity and speed, the Cooley-Tukey FFT algorithm, which is limited to composite sizes, is often chosen for the transform operation. In this case, d should be chosen as the smallest integer greater than the sum of the input polynomial degrees that is factorizable into small prime factors (e.g. 2, 3, and 5, depending upon the FFT implementation).

Some discrete Fourier transform pairs

In the following table

\omega_n

stands for

\exp(-2\pi i/n)

, a primitive n-th root of unity.

References

-
-
-
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Chapter 30: Polynomials and the FFT, pp.822–848, esp. section 30.2: The DFT and FFT, pp.830–838. Category:Fourier analysis Category:Digital signal processing Category:Numerical analysis Category:Transforms Category:Unitary operators ja:離散フーリエ変換

Mathematics

Mathematics is often defined as the study of topics such as quantity, structure, space, and change. Another view, held by many mathematicians, is that mathematics is the body of knowledge justified by deductive reasoning, starting from axioms and definitions. Practical mathematics, in nearly every society, is used for such purposes as accounting, measuring land, or predicting astronomical events. Mathematical discovery or research often involves discovering and cataloging patterns, without regard for application. The remarkable fact that the "purest" mathematics often turns out to have practical applications is what Eugene Wigner has called "the unreasonable effectiveness of mathematics." Today, the natural sciences, engineering, economics, and medicine depend heavily on new mathematical discoveries. The word "mathematics" comes from the Greek μάθημα (máthema) meaning "science, knowledge, or learning" and μαθηματικός (mathematikós) meaning "fond of learning". It is often abbreviated maths in Commonwealth English and math in North American English.

History

:Main article: History of mathematics The evolution of mathematics might be seen to be an ever-increasing series of abstractions, or alternatively an expansion of subject matter. The first abstraction was probably that of numbers. The realization that two apples and two oranges do have something in common, namely that they fill the hands of exactly one person, was a breakthrough in human thought. In addition to recognizing how to count concrete objects, prehistoric peoples also recognized how to count abstract quantities, like time -- days, seasons, years. Arithmetic (e.g. addition, subtraction, multiplication and division), naturally followed. Monolithic monuments testify to a knowledge of geometry. Further steps need writing or some other system for recording numbers such as tallies or the knotted strings called khipu used by the Inca empire to store numerical data. Numeral systems have been many and diverse. Historically, the major disciplines within mathematics arose, from the start of recorded history, out of the need to do calculations on taxation and commerce, to understand the relationships among numbers, to measure land, and to predict astronomical events. These needs can be roughly related to the broad subdivision of mathematics, into the studies of quantity, structure, space, and change. Mathematics since has been much extended, and there has been a fruitful interaction between mathematics and science, to the benefit of both. Mathematical discoveries have been made throughout history and continue to be made today.

Inspiration, pure and applied mathematics, and aesthetics

Mathematics arises wherever there are difficult problems that involve quantity, structure, space, or change. At first these were found in commerce, land measurement and later astronomy; nowadays, all sciences suggest problems studied by mathematicians, and many problems arise within mathematics itself. Newton invented infinitesimal calculus and Feynman his Feynman path integral using a combination of reasoning and physical insight, and today's string theory also inspires new mathematics. Some mathematics is only relevant in the area that inspired it, and is applied to solve further problems in that area. But often mathematics inspired by one area proves useful in many areas, and joins the general stock of mathematical concepts. As in most areas of study, the explosion of knowledge in the scientific age has led to specialization in mathematics. One major distinction is between pure mathematics and applied mathematics. Within applied mathematics, two major areas have split off and become disciplines in their own right, statistics and computer science. Many mathematicians talk about the elegance of mathematics, its intrinsic aesthetics and inner beauty. Simplicity and generality are valued. There is beauty also in a clever proof, such as Euclid's proof that there are infinitely many prime numbers, and in a numerical method that speeds calculation, such as the fast Fourier transform. G. H. Hardy in "A Mathematicians Apology" expressed the belief that these esthetic considerations are, in themselves, sufficient to justify the study of pure mathematics. Main article: Mathematical beauty.

Notation, language, and rigor

Mathematical writing is not easily accessible to the layperson. A Brief History of Time, Stephen Hawking's 1988 bestseller, contained a single mathematical equation. This was the author's compromise with the publisher's advice, that each equation would halve the sales. The reasons for the inaccessibility even of carefully-expressed mathematics can be partially explained. Contemporary mathematicians strive to be as clear as possible in the things they say and especially in the things they write (this they have in common with lawyers). They refer to rigor. To accomplish rigor, mathematicians have extended natural language. There is precisely-defined vocabulary for referring to mathematical objects, and stating certain common relations. There is an accompanying mathematical notation which, like musical notation, has a definite content and also has a strict grammar (under the influence of computer science, more often now called syntax). Some of the terms used in mathematics are also common outside mathematics, such as ring, group and category; but are not such that one can infer the meanings. Some are specific to mathematics, such as homotopy and Hilbert space. It was said that Henri Poincaré was only elected to the Académie Française so that he could tell them how to define automorphe in their dictionary. Rigor is fundamentally a matter of mathematical proof. Mathematicians want their theorems to follow mechanically from axioms by means of formal axiomatic reasoning. This is to avoid mistaken 'theorems', based on fallible intuitions; of which plenty of examples have occurred in the history of the subject (for example, in mathematical analysis). Axioms in traditional thought were 'self-evident truths', but that conception turns out not to be workable in pushing the mathematical boundaries. At a formal level, an axiom is just a string of symbols, which has an intrinsic meaning only in the context of all derivable formulas of an axiomatic system. It was the goal of Hilbert's program to put all of mathematics on a firm axiomatic basis, but according to Gödel's incompleteness theorem every (strong enough) axiom system has undecidable formulas; and so a final axiomatization of mathematics is unavailable. Nonetheless mathematics is often imagined to be (as far as its formal content) nothing but set theory in some axiomatization, in the sense that every mathematical statement or proof could be cast into formulas within set theory.

Is mathematics a science?

Carl Friedrich Gauss referred to mathematics as the Queen of the Sciences. The mathematician-physicist Leon M. Lederman has quipped: "The physicists defer only to mathematicians, and the mathematicians defer only to God (though you may be hard pressed to find a mathematician that modest)." If one considers science to be strictly about the physical world, then mathematics, or at least pure mathematics, is not a science. An alternative view is that certain scientific fields (such as theoretical physics) are mathematics with axioms that are intended to correspond to reality. In fact, the theoretical physicist, J. M. Ziman, proposed that science is public knowledge and thus includes mathematics. [http://info.med.yale.edu/therarad/summers/ziman.htm] In any case, mathematics shares much in common with many fields in the physical sciences, notably the exploration of the logical consequences of assumptions. Intuition and experimentation also play a role in the formulation of conjectures in both mathematics and the (other) sciences.

Overview of fields of mathematics

As noted above, the major disciplines within mathematics first arose out of the need to do calculations in commerce, to understand the relationships between numbers, to measure land, and to predict astronomical events. These four needs can be roughly related to the broad subdivision of mathematics into the study of quantity, structure, space, and change (i.e. arithmetic, algebra, geometry and analysis). In addition to these main concerns, there are also subdivisions dedicated to exploring links from the heart of mathematics to other fields: to logic, to set theory (foundations) and to the empirical mathematics of the various sciences (applied mathematics). The study of quantity starts with numbers, first the familiar natural numbers and integers and their arithmetical operations, which are characterized in arithmetic. The deeper properties of whole numbers are studied in number theory. The study of structure began with investigations of Pythagorean triples. Neolithic monuments on the British Isles are constructed using Pythagorean triples. Eventually, this led to the invention of more abstract numbers, such as the square root of two. The deeper structural properties of numbers are studied in abstract algebra and the investigation of groups, rings, fields and other abstract number systems. Included is the important concept of vectors, generalized to vector spaces and studied in linear algebra. The study of vectors combines three of the fundamental areas of mathematics, quantity, structure, and space. The study of space originates with geometry, beginning with Euclidean geometry. Trigonometry combines space and number. The modern study of space generalizes these ideas to include higher-dimensional geometry, non-Euclidean geometries (which play a central role in general relativity) and topology. Quantity and space both play a role in analytic geometry, differential geometry, and algebraic geometry. Within differential geometry are the concepts of fiber bundles, calculus on manifolds. Within algebraic geometry is the description of geometric objects as solution sets of polynomal equations, combining the concepts of quantity and space, and also the study of topological groups, which combine structure and space. Lie groups are used to study space, structure, and change. Topology in all its many ramifications may be the greatest growth area in 20th century mathematics. Understanding and describing change is a common theme in the natural sciences, and calculus was developed as a most useful tool. The central concept used to describe a changing quantity is that of a function. Many problems lead quite naturally to relations between a quantity and its rate of change, and the methods of differential equations. The numbers used to represent continuous quantities are the real numbers, and the detailed study of their properties and the properties of real-valued functions is known as real analysis. These have been generalized, with the inclusion of the square root of negative one, to the complex numbers, which are studied in complex analysis. Functional analysis focuses attention on (typically infinite-dimensional) spaces of functions. One of many applications of functional analysis is quantum mechanics. Many phenomena in nature can be described by dynamical systems; chaos theory makes precise the ways in which many of these systems exhibit unpredictable yet still deterministic behavior. Beyond quantity, structure, space, and change are areas of pure mathematics that can be approached only by deductive reasoning. In order to clarify the foundations of mathematics, the fields of mathematical logic and set theory were developed. Mathematical logic, which divides into recursion theory, model theory, and proof theory, is now closely linked to computer science. When electronic computers were first conceived, several essential theoretical concepts in computer science were shaped by mathematicians, leading to the fields of computability theory, computational complexity theory, and information theory. Many of those topics are now investigated in theoretical computer science. Discrete mathematics is the common name for the fields of mathematics most generally useful in computer science. An important field in applied mathematics is statistics, which uses probability theory as a tool and allows the description, analysis, and prediction of phenomena where chance plays a part. It is used in all the sciences. Numerical analysis investigates methods for using computers to efficiently solve a broad range of mathematical problems that are typically beyond human capacity, and taking rounding errors or other sources of error into account to obtain credible answers.

Major themes in mathematics

An alphabetical and subclassified list of mathematical topics is available. The following list of themes and links gives just one possible view. For a fuller treatment, see Areas of mathematics or the list of lists of mathematical topics.

Change

:Ways to express and handle change in mathematical functions, and changes between numbers. : :Arithmetic – Calculus – Vector calculus – Analysis – Differential equations – Dynamical systems – Chaos theory – List of functions

Foundations and methods

:Approaches to understanding the nature of mathematics. :philosophy of mathematics – mathematical intuitionism – mathematical constructivism – foundations of mathematics – set theory – symbolic logic – model theory – category theory – Logic – reverse mathematics – table of mathematical symbols

Discrete mathematics

:Discrete mathematics involves techniques that apply to objects that can only take on specific, separated values. : :Combinatorics – Naive set theory – Theory of computation– Cryptography – Graph theory

Applied mathematics

:Applied mathematics uses the full knowledge of mathematics to solve real-world problems. :Mathematical physics – Mechanics – Fluid mechanics – Numerical analysis – Optimization – Probability – Statistics – Mathematical economics – Financial mathematics – Game theory – Mathematical biology – Cryptography – Information theory

Important theorems

:These theorems have interested mathematicians and non-mathematicians alike. :See list of theorems for more :Pythagorean theorem – Fermat's last theorem – Gödel's incompleteness theorems – Fundamental theorem of arithmetic – Fundamental theorem of algebra – Fundamental theorem of calculus – Cantor's diagonal argument – Four color theorem – Zorn's lemma – Euler's identity – classification theorems of surfaces – Gauss-Bonnet theorem – Quadratic reciprocity – Riemann-Roch theorem.

Important conjectures

See list of conjectures for more :These are some of the major unsolved problems in mathematics. :Goldbach's conjecture – Twin Prime Conjecture – Riemann hypothesis – Poincaré conjecture – Collatz conjecture – P=NP? – open Hilbert problems.

History and the world of mathematicians

Mathematics and other fields

:Mathematics and architecture – Mathematics and education – Mathematics of musical scales

Common misconceptions

Mathematics is not a closed intellectual system, in which everything has already been worked out. There is no shortage of open problems. Pseudomathematics is a form of mathematics-like activity undertaken outside academia, and occasionally by mathematicians themselves. It often consists of determined attacks on famous questions, consisting of proof-attempts made in an isolated way (that is, long papers not supported by previously published theory). The relationship to generally-accepted mathematics is similar to that between pseudoscience and real science. The misconceptions involved are normally based on:
- misunderstanding of the implications of mathematical rigour;
- attempts to circumvent the usual criteria for publication of mathematical papers in a learned journal after peer review, with assumptions of bias;
- lack of familiarity with, and therefore underestimation of, the existing literature. The case of Kurt Heegner's work shows that the mathematical establishment is neither infallible, nor unwilling to admit error in assessing 'amateur' work. And like astronomy, mathematics owes much to amateur contributors such as Fermat and Mersenne. Mathematics is not accountancy. Although arithmetic computation is crucial to accountants, their main concern is to verify that computations are correct through a system of doublechecks. Advances in abstract mathematics are mostly irrelevant to the efficiency of concrete bookkeeping, but the use of computers clearly does matter. Mathematics is not numerology. Numerology uses modular arithmetic to reduce names and dates down to numbers, but assigns emotions or traits to these numbers intuitively or on the basis of traditions. Mathematical concepts and theorems need not correspond to anything in the physical world. In the case of geometry, for example, it is not relevant to mathematics to know whether points and lines exist in any physical sense, as geometry starts from axioms and postulates about abstract entities called "points" and "lines" that we feed into the system. While these axioms are derived from our perceptions and experience, they are not dependent on them. And yet, mathematics is extremely useful for solving real-world problems. It is this fact that led Eugene Wigner to write an essay on The Unreasonable Effectiveness of Mathematics in the Natural Sciences. Mathematics is not about unrestricted theorem proving, any more than literature is about the construction of grammatically correct sentences. However, theorems are elements of formal theories, and in some cases computers can generate proofs of these theorems more or less automatically, by means of automated theorem provers. These techniques have proven useful in formal verification of programs and hardware designs. However, they are unlikely to generate (in the near term, at least) mathematics with any widely recognized aesthetic value.

Bibliography

- Benson, Donald C., The Moment Of Proof: Mathematical Epiphanies (1999).
- Courant, R. and H. Robbins, What Is Mathematics? (1941);
- Davis, Philip J. and Hersh, Reuben, The Mathematical Experience. Birkhäuser, Boston, Mass., 1980. A gentle introduction to the world of mathematics.
- Boyer, Carl B., History of Mathematics, Wiley, 2nd edition 1998 available, 1st edition 1968 . A concise history of mathematics from the Concept of Number to contemporary Mathematics.
- Gullberg, Jan, Mathematics--From the Birth of Numbers. W.W. Norton, 1996. An encyclopedic overview of mathematics presented in clear, simple language.
- Hazewinkel, Michiel (ed.), Encyclopaedia of Mathematics. Kluwer Academic Publishers 2000. A translated and expanded version of a Soviet math encyclopedia, in ten (expensive) volumes, the most complete and authoritative work available. Also in paperback and on CD-ROM.
- Kline, M., Mathematical Thought from Ancient to Modern Times (1973).
- Pappas, Theoni, The Joy Of Mathematics (1989).

External links

- [http://www.cut-the-knot.org/ Interactive Mathematics Miscellany and Puzzles] — A collection of articles on various math topics, with interactive Java illustrations at cut-the-knot
- Rusin, Dave: [http://www.math-atlas.org/ The Mathematical Atlas]. A guided tour through the various branches of modern mathematics.
- Stefanov, Alexandre: [http://us.geocities.com/alex_stef/mylist.html Textbooks in Mathematics]. A list of free online textbooks and lecture notes in mathematics.
- Weisstein, Eric et al.: [http://www.mathworld.com/ MathWorld: World of Mathematics]. An online encyclopedia of mathematics.
- Polyanin, Andrei: [http://eqworld.ipmnet.ru/ EqWorld: The World of Mathematical Equations]. An online resource focusing on algebraic, ordinary differential, partial differential (mathematical physics), integral, and other mathematical equations.
- A mathematical thesaurus maintained by the [http://nrich.maths.org/ NRICH] project at the University of Cambridge (UK), [http://thesaurus.maths.org/ Connecting Mathematics]
- [http://planetmath.org/ Planet Math]. An online math encyclopedia under construction, focusing on modern mathematics. Uses the GFDL, allowing article exchange with Wikipedia. Uses TeX markup.
- [http://www.mathforge.net/ Mathforge]. A news-blog with topics ranging from popular mathematics to popular physics to computer science and education.
- [http://www.youngmath.net/concerns Young Mathematicians Network (YMN)]. A math-blog "Serving the Community of Young Mathematicians". Topics include: Math News, Grad and Undergrad Life, Job Search, Career, Work & Family, Teaching, Research, Misc...
- [http://metamath.org/ Metamath]. A site and a language, that formalize math from its foundations.
- [http://world.std.com/~reinhold/dir/mathmovies.html Math in the Movies]. A guide to major motion pictures with scenes of real mathematics
- [http://math.cofc.edu/faculty/kasman/MATHFICT/default.html Mathematics in fiction]. Links to works of fiction that refer to mathematics or mathematicians.
- [http://www.mathhelpforum.com/math-help Math Help Forum]. A forum, for math help, math discussion and debate.
- [http://www.sosmath.com/CBB S.O.S. Mathematics Cyberboard] a math help forum which incorporates a LaTeX extension, making it easier for members to write and display math formulae.
- [http://www-history.mcs.st-and.ac.uk/~history/ Mathematician Bibliography]. Extensive history and quotes from all famous mathematicians.
- [http://www.physicsmathforums.com/ Physics Math Forums]
- Category:School subjects fiu-vro:Matõmaatiga zh-min-nan:Sò·-ha̍k ko:수학 ms:Matematik ja:数学 simple:Mathematics th:คณิตศาสตร์

Digital signal processing

Digital signal processing (DSP) is the study of signals in a digital representation and the processing methods of these signals. DSP and analog signal processing are subfields of signal processing. DSP has three major subfields: audio signal processing, digital image processing and speech processing. Since the goal of DSP is usually to measure or filter continuous real-world analog signals, the first step is usually to convert the signal from an analog to a digital form, by using an analog to digital converter. Often, the required output signal is another analog output signal, which requires a digital to analog converter. The algorithms required for DSP are sometimes performed using specialized computers, which make use of specialized microprocessors called digital signal processors (also abbreviated DSP). These process signals in real time and are generally purpose-designed ASICs.

DSP domains

In DSP, engineers usually study digital signals in one of the following domains: time domain (one-dimensional signals), spatial domain (multidimensional signals), frequency domain, autocorrelation domain, and wavelet domains. They choose the domain in which to process a signal by making an educated guess (or by trying different possibilities) as to which domain best represents the essential characteristics of the signal. A sequence of samples from a measuring device produces a time or spatial domain representation, whereas a discrete Fourier transform produces the frequency domain information, that is the frequency spectrum. Autocorrelation is defined as the cross-correlation of the signal with itself over varying intervals of time or space.

Signal sampling

Main article: Sampling (signal processing) With the increasing use of computers the usage and need of digital signal processing has increased. In order to use an analog signal on a computer it must be digitized with an analog to digital converter (ADC). Sampling is usually carried out in two stages, discretization and quantization. In the discretization stage, the space of signals is partioned into equivalence classes and discretization is carried out by replacing the signal with representative signal of the corresponding equivalence class. In the quantization stage the representative signal values are approximated by values from a finite set. In order to properly sample an analog signal the Nyquist-Shannon sampling theorem must be satisfied. In short, the sampling frequency must be greater than twice the bandwidth of the signal (provided it is filtered appropriately). A digital to analog converter (DAC) is used to convert the digital signal back to analog. The use of a digital computer is a key ingredient into digital control systems.

Time and space domains

The most common processing approach in the time or space domain is enhancement of the input signal through a method called filtering. Filtering generally consists of some transformation of a number of surrounding samples around the current sample of the input or output signal. There are various ways to characterize filters; for example:
- A "linear" filter is a linear transformation of input samples; other filters are "non-linear." Linear filters satisfy the superposition condition, i.e. if an input is a weighted linear combination of different signals, the output is an equally weighted linear combination of the corresponding output signals.
- A "causal" filter uses only previous samples of the input or output signals; while a "non-causal" filter uses future input samples. A non-causal filter can be changed into a causal filter by adding a delay to it.
- A "time-invariant" filter has constant properties over time; other filters such as adaptive filters change in time.
- Some filters are "stable", others are "unstable". A stable filter produces an output that converges to a constant value with time, or remains bounded within a finite interval. An unstable filter produces output which diverges.
- A "finite impulse response" (FIR) filter uses only the input signal, while an "infinite impulse response" filter (IIR) uses both the input signal and previous samples of the output signal. FIR filters are always stable, while IIR filters may be unstable. Most filters can be described in Z-domain (a superset of the frequency domain) by their transfer functions. A filter may also be described as a difference equation, a collection of zeroes and poles or, if it is an FIR filter, an impulse response or step response. The output of an FIR filter to any given input may be calculated by convolving the input signal with the impulse response. Filters can also be represented by block diagrams which can then be used to derive a sample processing algorithm to implement the filter using hardware instructions.

Frequency domain

Signals are converted from time or space domain to the frequency domain usually through the Fourier transform. The Fourier transform converts the signal information to a magnitude and phase component of each frequency. Often the Fourier transform is converted to the power spectrum, which is the magnitude of each frequency component squared. The most common purpose for analysis of signals in the frequency domain is analysis of signal properties. The engineer can study the spectrum to get information of which frequencies are present in the input signal and which are missing. There are some commonly used frequency domain transformations. For example, the cepstrum converts a signal to the frequency domain through Fourier transform, takes the logarithm, then applies another Fourier transform. This emphasises the frequency components with smaller magnitude while retaining the order of magnitudes of frequency components.

Applications

The main applications of DSP are audio signal processing, audio compression, digital image processing, video compression, speech processing, speech recognition and digital communications. Specific examples are speech compression and transmission in digital mobile phones, equalisation of sound in Hifi equipment, weather forecasting, economic forecasting, seismic data processing, analysis and control of industrial processes, computer-generated animations in movies, medical imaging such as CAT scans and MRI, image manipulation, and digital effects for use with electric guitar amplifiers. A further application is very low frequency (VLF) reception with a PC soundcard [http://www.vlf.it/harald/strangerec.htm].

Techniques

- Bilinear transform
- Discrete Fourier transform
- Discrete-time Fourier transform
- Filter design
- LTI system theory
- Minimum phase
- Transfer function
- Z-transform
- Goertzel algorithm

References

- Alan V. Oppenheim, Ronald W. Schafer, John R. Buck : Discrete-Time Signal Processing, Prentice Hall, ISBN 0-13-754920-2
- Richard G. Lyons: Understanding Digital Signal Processing, Prentice Hall, ISBN 0131089897
- Sen M. Kuo, Woon-Seng Gan: Digital Signal Processors: Architectures, Implementations, and Applications, Prentice Hall, ISBN 0130352144
- Bernard Mulgrew, Peter Grant, John Thompson: Digital Signal Processing - Concepts and Applications, Palgrave Macmillan, ISBN 0-333-96356-3
- Steven W. Smith: Digital Signal Processing - A Practical Guide for Engineers and Scientists, Newnes, ISBN 0-7506-7444-X
- Paul A. Lynn, Wolfgang Fuerst: Introductory Digital Signal Processing with Computer Applications, John Wiley & Sons, ISBN 0-471-97984-8
- James D. Broesch: Digital Signal Processing Demystified, Newnes, ISBN 1878707167
- John Proakis, Dimitris Manolakis: Digital Signal Processing - Principles, Algorithms and Applications, Pearson, ISBN 0133942899
- Hari Krishna Garg: Digital Signal Processing Algorithms, CRC Press, ISBN 0849371783
- P. Gaydecki: Foundations Of Digital Signal Processing: Theory, Algorithms And Hardware Design, Institution of Electrical Engineers, ISBN 0852964315
- Paul M. Embree, Damon Danieli: C++ Algorithms for Digital Signal Processing, Prentice Hall, ISBN 0131791443
- Anthony Zaknich: Neural Networks for Intelligent Signal Processing, World Scientific Pub Co Inc, ISBN 9812383050
- Vijay Madisetti, Douglas B. Williams: The Digital Signal Processing Handbook, CRC Press, ISBN 0849385725
- Stergios Stergiopoulos: Advanced Signal Processing Handbook: Theory and Implementation for Radar, Sonar, and Medical Imaging Real-Time Systems, CRC Press, ISBN 0849336910
- Joyce Van De Vegte: Fundamentals of Digital Signal Processing, Prentice Hall, ISBN 0130160776
- Ashfaq Khan: Digital Signal Processing Fundamentals, Charles River Media, ISBN 1584502819
- Jonathan M. Blackledge, Martin Turner: Digital Signal Processing: Mathematical and Computational Methods, Software Development and Applications, Horwood Publishing, ISBN 1898563489
- Bimal Krishna, K. Y. Lin, Hari C. Krishna: Computational Number Theory & Digital Signal Processing, CRC Press, ISBN 0849371775
- Doug Smith: Digital Signal Processing Technology: Essentials of the Communications Revolution, American Radio Relay League, ISBN 0872598195
- Henrique S. Malvar: Signal Processing with Lapped Transforms, Artech House Publishers, ISBN 0890064679
- Charles A. Schuler: Digital Signal Processing: A Hands-On Approach, McGraw-Hill, ISBN 0078297443
- James H. McClellan, Ronald Schafer, Mark A. Yoder: Signal Processing First, Prentice Hall, ISBN 0130909998
- Artur Krukowski, Izzet Kale: DSP System Design: Complexity Reduced Iir Filter Implementation for Practical Applications, Kluwer Academic Publishers, ISBN 1402075588
- John G. Proakis: A Self-Study Guide for Digital Signal Processing, Prentice Hall, ISBN 0131432397

External links

- [http://Microcontroller.com Microcontroller.com]
- [http://www.dspguide.com The Scientist and Engineer's Guide to Digital Signal Processing]
- [http://www.dsprelated.com DSP related discussion groups ]
- [http://www.altera.com/technology/dsp/dsp-index.jsp FPGA based DSP dev kit]
- [http://www.dsptutor.freeuk.com/ Digital Signal Processing Tutorial]
- [http://www.bdti.com/faq/dsp_faq.htm FAQ on Digital Signal Processing]
- [http://www.tapr.org/tapr/html/dspf.html Introduction to Digital Signal Processing]
- [http://www.cdsp.neu.edu/ CDSP - Center for Digital Signal Processing]
- [http://www.musicdsp.org Music DSP Source Code Archive]
- [http://users.aber.ac.uk/dgw/dsp.htm DSP links]
- [http://www.bores.com/courses/intro/ Yet another good DSP tutorial (bores) ]
- [http://www.spectrum-analyzer.info Spectrum Analysis Tutorials]
- [http://www.k9spud.com/traxmod/ TRAXMOD dsPIC MOD music player]
- [http://www.devicetools.com DeviceTools] - Tools and silicon for embedded device developers
- [http://www.digitalfilterdesign.com Free digital filter design software] Category:Digital electronics
- ja:デジタル信号処理 th:การประมวลผลสัญญาณดิจิทัล

Partial differential equations

In mathematics, a partial differential equation (PDE) is an equation relating the partial derivatives of an unknown function of several variables. A solution of the equation is a function satisfying this relation. The idea is to try to deduce information about an unknown function by first discovering a relationship between itself and its partial derivatives in the form of a PDE. The PDE can then be used to uncover information about the unknown function, and sometimes an explicit formula for the unknown function can be discovered. A PDE usually has many (possibly infinitely many) solutions; a particular problem often requires additional boundary conditions which constrain the solution set. Where ordinary differential equations have solutions that are families with each solution characterized by the values of some parameters, for a PDE the solutions often are parametrized by functions (informally put, this means that the set of solutions is much larger). Partial differential equations are ubiquitous in science and especially in physics, as physical laws can usually be written in form of PDEs. They describe phenomena such as fluid flow, the growth of crystals, diffusion, gravitation, and the behavior of electromagnetic fields. They are important in fields such as aircraft simulation, computer graphics, and weather prediction. The central equations of general relativity and quantum mechanics are also partial differential equations.

Notation and examples

In PDEs, it is common to write the unknown function as u and its partial derivative with respect to the variable x as u_x, that is: :

u_x =

u_ =

Especially in (mathematical) physics, one often prefers use of the nabla operator

\nabla=(\part_x,\part_y,\part_z)

for spatial derivatives and a dot (

\dot u

) for time derivatives, e.g. to write the wave equation (see below) as

\ddot u=c^2\nabla^2u

Laplace's equation

A very important and basic PDE is Laplace's equation: :

u_ + u_ + u_ = 0

for the unknown function u(x,y,z). Solutions to this equation, known as harmonic functions, serve as the potentials of vector fields in physics, such as the gravitational or electrostatic fields. A generalization of Laplace's equation is Poisson's equation: :

u_ + u_ + u_ = f

where f(x,y,z) is a given function. The solutions to this equation describe potentials of gravitational and electrostatic fields in the presence of masses or electrical charges, respectively.

Wave equation

The wave equation is an equation for an unknown function u(x,y,z,t) (where we think of t as a time variable) which reads: :

u_ = c^2( u_ + u_ + u_ )

Its solutions describe waves such as sound or light waves; c is a number which represents the speed of the wave. In lower dimensions, this equation describes the vibration of a string or drum. Solutions will typically be combinations of oscillating sine waves.

Heat equation

The heat equation describes the temperature in a given region over time. It is: :

u_t = k ( u_ + u_ + u_ )

Solutions will typically "even out" over time. The number k describes the thermal diffusivity of the material.

Euler-Tricomi equation

The Euler-Tricomi equation is used in the investigation of transonic flow. It is :

u_=xu_

Advection equation

The advection equation describes the transport of a conserved scalar

\psi

in a velocity field

=(u,v,w)

. It is: :

\psi_t+(u\psi)_x+(v\psi)_y+(w\psi)_z=0.

If the velocity field is solenoidal (that is,

\nabla\cdot=0

), then the equation may be simplified to :

\psi_t+u\psi_x+v\psi_y+w\psi_z=0.

The one dimensional steady flow advection equation

\psi_t+u.\psi_x=0

(where

u

is constant) is commonly referred to as the pigpen problem. If

u

is not constant and equal to

\psi

the equation is referred to as Burgers' equation.

Ginzburg-Landau equation

The Ginzburg-Landau equation is used in modelling superconductivity. It is :

iu_t+pu_ +q|u|^2u=i\gamma u

where

p,q\in\mathbb

and

\gamma\in\mathbb

are constants and

i

is the imaginary unit.

The Dym equation

The Dym equation is named for Harry Dym and occurs in the study of solitons. It is :

u_t = u^3u_.

Other examples

The Schrödinger equation is a PDE at the heart of non-relativistic quantum mechanics. In the WKB approximation it is the Hamilton-Jacobi equation. Except for the Dym equation and the Ginzburg-Landau equation, the above equations are linear in the sense that they can be written in the form Au = f for a given linear operator A and a given function f. Other important non-linear equations include the Navier-Stokes equations describing the flow of fluids, and Einstein's field equations of general relativity.

Methods to solve PDEs

Linear PDEs are generally solved, when possible, by decomposing the equation according to a set of basis functions, solving those individually and using superposition to find the solution corresponding to the boundary conditions. The method of separation of variables has many important particular applications. There are no generally applicable methods to solve non-linear PDEs. Still, existence and uniqueness results (such as the Cauchy-Kovalevskaya theorem) are often possible, as are proofs of important qualitative and quantitative properties of solutions (getting these results is a major part of analysis). Nevertheless, some techniques can be used for several types of equations. The h-principle is the most powerful method to solve underdetermined equations. The Riquier-Janet theory is an effective method for obtaining information about many analytic overdetermined systems. The method of characteristics can be used in some very special cases to solve partial differential equations. In some cases, a PDE can be solved via perturbation analysis in which the solution is considered to be a correction to an equation with a known solution. Alternatives are numerical analysis techniques from simple finite difference schemes to the more mature multigrid and finite element methods. Many interesting problems in science and engineering are solved in this way using computers, sometimes high performance supercomputers.

Classification

Second-order partial differential equations, and systems of second-order PDEs, can usually be classified as parabolic, hyperbolic or elliptic. This classification gives an intuitive insight into the behavior of the system itself. Assuming

u_=u_,

the general second-order PDE is of the form :

Au_ + Bu_ + Cu_ + \cdots = 0,

which looks remarkably similar to the equation for a conic section: :

Ax^2 + Bxy + Cy^2 + \cdots = 0.

Just as one classifies conic sections into parabolic, hyperbolic, and elliptic based on the discriminant

B^2 - 4AC

, the same can be done for a second-order PDE. #

B^2 - 4AC < 0

: elliptic equations tend to smooth out any disturbances. A typical example is Laplace's equation. The motion of a fluid at sub-sonic speeds can be approximated with elliptic PDEs. #

B^2 - 4AC = 0

: parabolic equations tend to smooth out any pre-existing disturbances in the data. A typical example is the heat equation. #

B^2 - 4AC > 0

: hyperbolic equations tend to amplify any disturbances in the data. A typical example is the wave equation. The motion of a fluid at super-sonic speeds can be approximated with hyperbolic PDEs. This method of classification can easily be extended to equations with more than two independent variables by examining the eigenvalues of the coefficient matrix. In this situation, the classification scheme becomes: # Elliptic: The eigenvalues are all positive or all negative. # Parabolic : The eigenvalues are all positive or all negative, save one which is zero. # Hyperbolic : There is at least one negative and at least one positive eigenvalue, and none of the eigenvalues are zero. This matches with positive-definite and negative-definite matrix analysis, of the sort that comes up during a discussion of maxima and minima.

Equations of mixed type

If a PDE has coefficients which are not constant, it is possible that it will not belong to any of these categories but rather be of mixed type. A simple but important example is the Euler-Tricomi equation :

u_=xu_

which is called elliptic-hyperbolic because it is elliptic in the region x < 0, hyperbolic in the region x > 0, and degenerate parabolic on the line x = 0.

External links

- [http://eqworld.ipmnet.ru/en/pde-en.htm Partial Differential Equations: Exact Solutions] at EqWorld: The World of Mathematical Equations.
- [http://eqworld.ipmnet.ru/en/solutions/eqindex/eqindex-pde.htm Partial Differential Equations: Index] at EqWorld: The World of Mathematical Equations.
- [http://eqworld.ipmnet.ru/en/methods/meth-pde.htm Partial Differential Equations: Methods] at EqWorld: The World of Mathematical Equations.
- [http://www.exampleproblems.com/wiki/index.php?title=Partial_Differential_Equations Example problems with solutions] at exampleproblems.com

References

- L.C. Evans, Partial Differential Equations, American Mathematical Society, Providence, 1998. ISBN 0-8218-0772-2
- A. D. Polyanin, Handbook of Linear Partial Differential Equations for Engineers and Scientists, Chapman & Hall/CRC Press, Boca Raton, 2002. ISBN 1-58488-299-9
- A. D. Polyanin and V. F. Zaitsev, Handbook of Nonlinear Partial Differential Equations, Chapman & Hall/CRC Press, Boca Raton, 2004. ISBN 1-58488-355-3
- A. D. Polyanin, V. F. Zaitsev, and A. Moussiaux, Handbook of First Order Partial Differential Equations, Taylor & Francis, London, 2002. ISBN 0-415-27267-X
- D. Zwillinger, Handbook of Differential Equations (3rd edition), Academic Press, Boston, 1997. Category:Multivariate calculus
- ja:偏微分方程式

Convolution

For the computer science usage see convolution (computer science) . ---- In mathematics and in particular, functional analysis, convolution is a mathematical operator which takes two functions f and g and produces a third function that in a sense represents the amount of overlap between f and a reversed and translated version of g. A convolution is a kind of very general moving average, as one can see by taking one of the functions to be an indicator function of an interval.

Uses

Convolution and related operations are found in many applications of engineering and mathematics.
- In statistics, as noted above, a weighted moving average is a convolution.
- In statistics, the probability distribution of the sum of two independent random variables is the convolution of each of their distributions.
- In optics, many kinds of "blur" are described by convolutions. A shadow (e.g. the shadow on the table when you hold your hand between the table and a light source) is the convolution of the shape of the light source that is casting the shadow and the object whose shadow is being cast. An out-of-focus photograph is the convolution of the sharp image with the blur circle formed by the iris diaphragm.
- In acoustics, an echo is the convolution of the original sound with a function representing the various objects that are reflecting it.
- In artificial reverberation (digital signal processing, pro audio), convolution is used to map the impulse response of a real room on a digital audio signal (see previous and next point for additional information).
- In electrical engineering and other disciplines, the output (response) of a (stationary, or time- or space-invariant) linear system is the convolution of the input (excitation) with the system's response to an impulse or Dirac delta function. See LTI system theory and digital signal processing.
- In time-resolved fluorescence spectroscopy, the excitation signal can be treated as a chain of delta pulses, and the measured fluorescence is sum of exponential decays from each delta pulse.
- In physics, wherever there is a linear system with a "superposition" principle, a convolution operation makes an appearance.

Definition

The convolution of f and g is written

f - g

. It is defined as the integral of the product of the two functions after one is reversed and shifted. :

(f   -  g )(t) = \int f(\tau) g(t - \tau)\, d\tau

The integration range depends on the domain on which the functions are defined. While the symbol

t

is used above, it need not represent the time domain. In the case of a finite integration range, f and g are often considered to extend periodically in both directions, so that the term g(t − τ) does not imply a range violation. This use of periodic domains is sometimes called a cyclic, circular or periodic convolution. Of course, extension with zeros is also possible. Using zero-extended or infinite domains is sometimes called a linear convolution, especially in the discrete case below. If

X

and

Y

are two independent random variables with probability distributions f and g, respectively, then the probability distribution of the sum

X + Y

is given by the convolution f

-

g. For discrete functions, one can use a discrete version of the convolution. It is then given by :

(f   -  g)(m) = \sum_n  \,

When multiplying two polynomials, the coefficients of the product are given by the convolution of the original coefficient sequences, in this sense (using extension with zeros as mentioned above). Generalizing the above cases, the convolution can be defined for any two integrable functions defined on a locally compact topological group. A different generalization is the convolution of distributions.

Properties

The various convolution operators all satisfy the following properties:

Commutativity

f  -  g = g  -  f \,

Associativity

f   -  (g   -  h) = (f   -  g)   -  h \,

Distributivity

f   -  (g + h) = (f   -  g) + (f   -  h) \,

Associativity with scalar multiplication

a (f   -  g) = (a f)   -  g = f   -  (a g) \,

for any real (or complex) number

a

. Differentiation rule: :

\mathcal(f   -  g) = \mathcalf   -  g = f   -  \mathcalg \,

where Df denotes the derivative of f or, in the discrete case, the difference operator
Df(n) = f(n+1) - f(n).

Convolution theorem

The convolution theorem states that :

\mathcal(f   -  g) =  \mathcal (f) \cdot \mathcal (g)

where F(f) denotes the Fourier transform of f. Versions of this theorem also hold for the Laplace transform, two-sided Laplace transform and Mellin transform.

Convolutions on groups

If G is a suitable group endowed with a measure m (for instance, a locally compact Hausdorff topological group with the Haar measure) and if f and g are real or complex valued m-integrable functions of G, then we can define their convolution by :

(f   -  g)(x) = \int_G f(y)g(xy^)\,dm(y) \,

In this case, it is also possible to give, for instance, a Convolution Theorem, however it is much more difficult to phrase and requires representation theory for these types of groups and the Peter-Weyl theorem of Harmonic analysis. It is very difficult to do these calculations without more structure, and Lie groups turn out to be the setting in which these things are done.

External links

-
- http://www.jhu.edu/~signals/convolve/index.html Visual convolution Java Applet. category:functional analysis Category:Image processing ja:畳み込み

Fast Fourier transform

A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. FFTs are of great importance to a wide variety of applications, from digital signal processing to solving partial differential equations to algorithms for quickly multiplying large integers. This article describes the algorithms, of which there are many; see discrete Fourier transform for properties and applications of the transform. Let x₀, ...., x_n-1 be complex numbers. The DFT is defined by the formula :

f_j =  \sum_^ x_k e^
\qquad
j = 0,\dots,n-1.

Evaluating these sums directly would take O(n²) arithmetical operations (see Big O notation). An FFT is an algorithm to compute the same result in only O(n log n) operations. In general, such algorithms depend upon the factorization of n, but (contrary to popular misconception) there are O(n log n) FFTs for all n, even prime n. Since the inverse DFT is the same as the DFT, but with the opposite sign in the exponent and a 1/n factor, any FFT algorithm can easily be adapted for it as well.

The Cooley-Tukey algorithm

Main article: Cooley-Tukey FFT algorithm. By far the most common FFT is the Cooley-Tukey algorithm. This is a divide and conquer algorithm that recursively breaks down a DFT of any composite size n = n₁n₂ into many smaller DFTs of sizes n₁ and n₂, along with O(n) multiplications by complex roots of unity traditionally called twiddle factors. This method (and the general idea of an FFT) was popularized by a publication of J. W. Cooley and J. W. Tukey in 1965, but it was later discovered that those two authors had independently re-invented an algorithm known to Carl Friedrich Gauss around 1805 (and subsequently rediscovered several times in limited forms). The most well-known use of the Cooley-Tukey algorithm is to divide the transform into two pieces of size

n / 2

at each step, and is therefore limited to power-of-two sizes, but any factorization can be used in general (as was known to both Gauss and Cooley/Tukey). These are called the radix-2 and mixed-radix cases, respectively (and other variants have their own names as well). Although the basic idea is recursive, most traditional implementations rearrange the algorithm to avoid explicit recursion. Also, because the Cooley-Tukey algorithm breaks the DFT into smaller DFTs, it can be combined arbitrarily with any other algorithm for the DFT, such as those described below.

Other FFT algorithms

Main articles: Prime-factor FFT algorithm, Bruun's FFT algorithm, Rader's FFT algorithm, Bluestein's FFT algorithm. There are other FFT algorithms distinct from Cooley-Tukey. For

n = n_1n_2

with coprime

n_1

and

n_2

, one can use the Prime-Factor (Good-Thomas) algorithm (PFA), based on the Chinese Remainder Theorem, to factorize the DFT similarly to Cooley-Tukey but without the twiddle factors. The Rader-Brenner algorithm (1976) is a Cooley-Tukey-like factorization but with purely imaginary twiddle factors, reducing multiplications at the cost of increased additions and reduced numerical stability. Algorithms that recursively factorize the DFT into smaller operations other than DFTs include the Bruun and QFT algorithms. (The Rader-Brenner and QFT algorithms were proposed for power-of-two sizes, but it is possible that they could be adapted to general composite

n

. Bruun's algorithm applies to arbitrary even composite sizes.) Bruun's algorithm, in particular, is based on interpreting the FFT as a recursive factorization of the polynomial

z^n-1

, here into real-coefficient polynomials of the form

z^m-1

and

z^ + az^m + 1

. Another polynomial viewpoint is exploited by the Winograd algorithm, which factorizes

z^n-1

into cyclotomic polynomials—these often have coefficients of 1, 0, or −1, and therefore require few (if any) multiplications, so Winograd can be used to obtain minimal-multiplication FFTs and is often used to find efficient algorithms for small factors. Indeed, Winograd showed that the DFT can be computed with only

O(n)

multiplications, leading to a proven achievable lower bound on the number of irrational multiplications for power-of-two sizes; unfortunately, this comes at the cost of many more additions, a tradeoff no longer favorable on modern processors with hardware multipliers. In particular, Winograd also makes use of the PFA as well as an algorithm by Rader for FFTs of prime sizes. Rader's algorithm, exploiting the existence of a generator for the multiplicative group modulo prime

n

, expresses a DFT of prime size

n

as a cyclic convolution of (composite) size

n-1

, which can then be computed by a pair of ordinary FFTs via the convolution theorem (although Winograd uses other convolution methods). Another prime-size FFT is due to L. I. Bluestein, and is s

Discrete Fourier transform

Properties

Completeness

Orthogonality

The Plancherel theorem and Parseval's theorem

The shift theorem

Periodicity and aliasing

Circular convolution theorem and cross-correlation theorem

Relationship to trigonometric interpolation polynomials

The unitary DFT

Expressing the inverse DFT in terms of the DFT

The real DFT

Generalized DFT

Multidimensional DFT

Applications

Spectral analysis

Data compression

Partial differential equations

Multiplication of large integers

Outline of DFT polynomial multiplication algorithm

Some discrete Fourier transform pairs

References

Mathematics

History

Inspiration, pure and applied mathematics, and aesthetics

Notation, language, and rigor

Is mathematics a science?

Overview of fields of mathematics

Major themes in mathematics

Quantity

Structure

Space

Change

Foundations and methods

Discrete mathematics

Applied mathematics

Important theorems

Important conjectures

History and the world of mathematicians

Mathematics and other fields

Common misconceptions

See also

Bibliography

External links

Digital signal processing

DSP domains

Signal sampling

Time and space domains

Frequency domain

Applications

Techniques

Related fields

References

External links

Partial differential equations

Notation and examples

Laplace's equation

Wave equation

Heat equation

Euler-Tricomi equation

Advection equation

Ginzburg-Landau equation

The Dym equation

Other examples

Methods to solve PDEs

Classification

Equations of mixed type

External links

References

Convolution

Uses

Definition

Properties

Commutativity

Associativity

Distributivity

Associativity with scalar multiplication

Convolution theorem

Convolutions on groups

See also