📄 node4.html
字号:
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.2//EN"><!--Converted with LaTeX2HTML 96.1-h (September 30, 1996) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds --><HTML><HEAD><TITLE>General computational issues</TITLE><META NAME="description" CONTENT="General computational issues"><META NAME="keywords" CONTENT="TiseanHTML"><META NAME="resource-type" CONTENT="document"><META NAME="distribution" CONTENT="global"><LINK REL=STYLESHEET HREF="TiseanHTML.css"></HEAD><BODY bgcolor=ffffff LANG="EN" > <A NAME="tex2html105" HREF="node5.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="icons/next_motif.gif"></A> <A NAME="tex2html103" HREF="node2.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="icons/up_motif.gif"></A> <A NAME="tex2html99" HREF="node3.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="icons/previous_motif.gif"></A> <BR><B> Next:</B> <A NAME="tex2html106" HREF="node5.html">Phase space representation</A><B>Up:</B> <A NAME="tex2html104" HREF="node2.html">Introduction</A><B> Previous:</B> <A NAME="tex2html100" HREF="node3.html">Philosophy of the TISEAN </A><BR> <P><H2><A NAME="SECTION00022000000000000000">General computational issues</A></H2><A NAME="secgeneral"> </A>The natural basis to formulate nonlinear time series algorithms from chaostheory is a multi-dimensional phase space, rather than the time or thefrequency domain. It will be essential for the global dynamics in this phasespace to be nonlinear in order to fulfill the constraints of non-triviality andboundedness. Only in particular cases this nonlinear structure will be easilyrepresentable by a global nonlinear function. Instead, all properties will beexpressed in terms of local quantities, often by suitable global averages. Alllocal information will be gained from neighborhood relations of various kindsfrom time series elements. Thus a recurrent computational issue will be thatof defining local neighborhoods in phase space. Finding neighbors inmultidimensional space is a common problem of computationalgeometry. Multidimensional tree structures are widely used and have attractivetheoretical properties. Finding all neighbors in a set of <I>N</I> vectorstakes <I>O(</I>log<I>N)</I> operations, thus the total operation count is <I>O(N</I>log<I>N)</I>. A fastalternative that is particularly efficient for relatively low dimensionalstructures embedded in multidimensional spaces is given by box-assistedneighbor search methods which can push the operation count down to <I>O</I>(<I>N</I>)under certain assumptions. Both approaches are reviewed in Ref. [<A HREF="citation.html#neigh">20</A>]with particular emphasis on time series applications. In the TISEAN project,fast neighbor search is done using a box-assisted approach, as described inRef. [<A HREF="citation.html#KantzSchreiber">2</A>].<P>No matter in what space dimension we are working, we will define <EM>candidates</EM> for nearest neighbors in two dimensions using a grid of evenlyspaced boxes. With a grid of spacing <IMG WIDTH=6 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline6495" SRC="img3.gif">, all neighbors of a vector<IMG WIDTH=9 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline6497" SRC="img4.gif"> closer than epsilon must be located in the adjacent boxes. But not allpoints in the adjacent boxes are neighbors, they may be up to <IMG WIDTH=13 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline6499" SRC="img5.gif">away in two dimensions and arbitrarily far in higher dimensions. Neighborssearch is thus a two stage process. First the box-assisted data base has to befilled and then for each point a list of neighbors can be requested. There are a few instances where it is advisable to abandon the fast neighborsearch strategy. One example is the program <tt>noise</tt> that does nonlinear noisefiltering in a data stream. (This program is no longer maintained as part of TISEAN). It is supposed to start filtering soon after thefirst points have been recorded. Thus the neighbor data base cannot beconstructed in the beginning. Another exception is if quite short (<500points, say), high dimensional data are processed. Then the overhead for theneighbor search should be avoided and instead an optimized straight<i>O(N²)</i> method be used, like it is done in <a href="../docs_f/c2naive.html">c2naive</a>.<P>For portability, all programs expect time series data in column formatrepresented by ASCII numbers. The column to be processed can be specified onthe command line. Although somewhat wasteful for storing data, ASCII is theleast common divisor between the different ways most software can store data.All parameters can be set by adding options to the command, which, in manyprograms, just replace the default values. Obviously, relying on defaultsettings is particularly dangerous in such a subtle field. Since almost allroutines can read from standard input and write to standard output, programscan be part of pipelines. For example they can be called as filters from insidegraphics software or other software tools which are able to execute shellcommands. Also, data conversion or compression can be done ``on the fly'' thisway. The reader here realizes that we are speaking of UNIX or LINUX platformswhich seems to be the most appropriate environment. It is however expected thatmost of the programs will be ported to other environments in the near future.<P>For those readers familiar with the programs published inRef. [<A HREF="citation.html#KantzSchreiber">2</A>] we should mention that these form the basis for anumber of those TISEAN programs written in FORTRAN. The C programs, even ifthey do similar things, are fairly independent implementations. All C programs now use dynamic allocation of storage, for example.<P><HR><A NAME="tex2html105" HREF="node5.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="icons/next_motif.gif"></A> <A NAME="tex2html103" HREF="node2.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="icons/up_motif.gif"></A> <A NAME="tex2html99" HREF="node3.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="icons/previous_motif.gif"></A> <BR><B> Next:</B> <A NAME="tex2html106" HREF="node5.html">Phase space representation</A><B>Up:</B> <A NAME="tex2html104" HREF="node2.html">Introduction</A><B> Previous:</B> <A NAME="tex2html100" HREF="node3.html">Philosophy of the TISEAN </A><P><ADDRESS><I>Thomas Schreiber <BR>Wed Jan 6 15:38:27 CET 1999</I></ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -