Newsgroup sci.math.num-analysis 28547

Directory

aj@axis.jeack.com.au (AJ) says:
> Is there a formula that can be used to generate a sine wave 
> that does not use the SIN function.  I would like it to only 
> use adds/subtracts/multiplys/divides.
jmb184@servtech.com (John Bailey) wrote:
> Iterating two lines of code: x = x + y/k, y = y - x/k
> results in a series of points which outline a circular
> shape. It requires some tedious algebra to demonstrate
> precisely what is happening.  
I think the most direct approach to this kind of algorithm is
via the elementary trigonometric identities
          sin(a+b) = sin(a)cos(b) + cos(a)sin(b)
          cos(a+b) = cos(a)cos(b) - sin(a)sin(b)
To generate the sequence of sine (and/or cosine) values for the
angles 0, q, 2q, 3q, ...  for any desired angluar step size q,
we have the recursive formulas
       sin(nq)  =    A sin((n-1)q)  +  B cos((n-1)q)
       cos(nq)  =    A cos((n-1)q)  -  B sin((n-1)q)
where A=cos(q) and B=sin(q).  Thus, for any two constants A,B such
that A^2 + B^2 = 1  the above formulas (with initial values sin(0)=0
and cos(0)=1) will generate the sines and cosines of nq, n=1,2,3,...,
where q = arctan(B/A).
Of course we can eliminate either the sine or the cosine to give
the individual 2nd-order recurrences
         sin(nq)  =  2A sin((n-1)q)  -  sin((n-2)q)
         cos(nq)  =  2A cos((n-1)q)  -  cos((n-2)q)
  __________________________________________________________________
 |                /*\                                               |
 |   MathPages   /   \     http://www.seanet.com/~ksbrown/          |
 |______________/_____\_____________________________________________|

Hi all,
I have one problem which looks very nice but I am not sure if it
has nice solution.
Let a = [1 p q r s]',  //where ' means transpose
    b = [1 u v w z]'
and A = a*a';
Is there anu "shortcut" to solve the system
A*x = b;
i.e is it possible to solve it with less operations than using 
Gauss' (or some even more effective) procedure. 
Thanks a lot,
Miroslav
-- 
Dipl. Ing. Miroslav Trajkovic		phone:	+61 2 351-4824
Postgraduate Research Student		fax:	+61 2 351-3847
University of Sydney			
NSW 2006, Australia
e-mail: miroslav@ee.usyd.edu.au
http://www.ee.usyd.edu.au/~miroslav

               ********************************************
               *                                          *
               *             CALL FOR PAPERS              *
               *                                          *
               *    Thirteenth Annual ACM Symposium on    *
               *                                          *
               *          COMPUTATIONAL GEOMETRY          *
               *                                          *
               ********************************************
                 **** New: APPLIED CONFERENCE TRACK ****
                    June 4--6, 1997,     Nice, FRANCE
THE CONFERENCE NOW HAS TWO TRACKS: AN APPLIED TRACK, AND A THEORETICAL TRACK.
Papers and short communications are invited for submission.  These may
address either fundamental problems in geometric computing, or focus
on applications including, but not limited to
 o  robotics and virtual worlds,
 o  computer graphics,
 o  simulation and visualization,
 o  image processing,
 o  geometric and solid modeling,
 o  computer aided geometric design,
 o  manufacturing,
 o  geographical information systems.
The APPLIED TRACK welcomes submissions that are application-oriented,
including
    representational and algorithmic issues arising from applications
    and implementation considerations, case studies of algorithms in
    application contexts, etc.
Authors wishing to submit to this track should send 15 copies of an
extended abstract or paper or communication, to be received on or
before
    ***  DECEMBER 17, 1996  ***
to:
    Christoph M. Hoffmann
    Computer Science
    Purdue University
    West Lafayette, IN 47907-1398, USA
    cmh@cs.purdue.edu
    Tel: +1-317-494-6185
The THEORETICAL TRACK welcomes submissions that are
foundation-oriented including
    analysis of geometric algorithms and data structures, theoretical
    issues arising from implementations, geometric optimization,
    analysis of geometric configurations, etc.
Authors wishing to submit to this track should send 13 copies of an
extended abstract or communication, to be received on or before
    ***  DECEMBER 17, 1996  ***
to:
    Raimund Seidel
    Univ. des Saarlandes
    FB 14, Informatik, Geb. 45, Raum 410
    D-66123 Saarbruecken, GERMANY
    seidel@cs.uni-sb.de
    Tel: +49--681--302--4448
In doubtful cases submissions to one track may be forwarded to the
other for consideration, unless the authors have explicitly stated
interest in one track only.
Submissions received past the deadline risk rejection without further
consideration. Authors will be notified of acceptance or rejection by
February 19, 1997. A full version of each accepted contribution in
final form will be due by March 19, 1997, for inclusion in the
proceedings.  There will be joint proceedings, which will be
distributed at the Symposium and will be subsequently available for
purchase from ACM. A selection of accepted papers will be invited to
special issues of journals.
Papers must present original research. An extended abstract should
begin with a succinct statement of the problems/goals of the paper,
the main results, and the significance of the work in the context of
previous research. It should provide sufficient detail to allow the
program committee to evaluate the validity, quality, and relevance of
the contribution. The entire extended abstract should not exceed 10
double-spaced pages. An optional appendix may be included, but this
will be used at the program committee's discretion.
Communications are limited to three pages and will be published in a
separate section of the proceedings.  They are meant for reports on
experimental results, on experiences with applications of
computational geometry in real-world situations and other practical
issues that are relevant to computational geometry, as well as for
short notes of an algorithmic or combinatorial nature.  They will be
presented as posters (possibly with implementation demos) at the
conference.
Preceding the symposium there will be a two-day workshop on geometric
computing.  Check the symposium's WWW-page for more information:
    http://www.inria.fr/prisme/scg97
Conference Chair: Jean-Daniel Boissonnat,
                  (INRIA Sophia-Antipolis)
          e-mail: Jean-Daniel.Boissonnat@sophia.inria.fr
                        Program Committees
    Applied Track                             Theoretical Track
Bernard Chazelle (Princeton)              Nina Amenta (Xerox PARC)
Jung-Hong Chuang (Taiwan)                 Tetsuo Asano (Osaka Elect. Univ.) 
David Dobkin (Princeton)                  Ken Clarkson (Bell Labs)
Gerald Farin (Arizona State)              David Kirkpatrick (British Columbia)
Christoph Hoffmann (chair) (Purdue)       David Mount (Maryland)
Ming Lin (ARO)                            Stefan Naeher (Halle, Germany)
Joe Mitchell (SUNY Stony Brook)           Richard Pollack (NYU)
Nick Patrikalakis (MIT)                   Claude Puech (Grenoble)
Franco Preparata  (Brown)                 Guenter Rote (Graz, Austria)
Jarek Rossignac (Georgia Tech.)           Otfried Schwarzkopf (Pohang U)
Hans Peter Seidel (Erlangen, Germany)     Raimund Seidel (chair)(Saarland)
Vadim Shapiro (Wisconsin)
Tamas Varady (Hungarian Academy of Sci)
                              CALL FOR VIDEOS
             6th Annual Video Review of Computational Geometry
                           To be presented at the
                     Thirteenth Annual ACM Symposium on
                           COMPUTATIONAL GEOMETRY
                               June 4-6, 1997
                                Nice, FRANCE
Videos are sought for a video review of computational geometry.
BACKGROUND: This video review showcases the use of computer graphics
in computational geometry for exposition and education, as an
interface and a debugging tool in software development, and for the
visual exploration of geometry in research. Algorithm animations,
visual explanations of structural theorems, descriptions of
applications of computational geometry, and demonstrations of software
systems are all appropriate. Videos that accompany papers or
communications submitted to the technical program committee are
encouraged.
SUBMISSIONS: Authors should send one preview copy of a videotape to
the address below by February 15, 1997. The videotape should be at
most eight minutes long (three to five minutes, preferred), and be in
VHS NTSC (preferred) or VHS PAL format.
Each video tape must be accompanied by five (5) copies of a one- or
two-page description of the material shown in the video and the
techniques used in the implementation. Please format descriptions
following the guidelines for ACM proceedings.
Additional materials describing the content of the videos, such as the
full text of accompanying papers, may be included.
Videotapes and accompanying text should be sent to:
	SoCG'96 Video Review Committee
	c/o: Jack Snoeyink
	UBC Computer Science
	2366 Main Mall, rm 201
	Vancouver, BC, V6T 1Z4, Canada
For customs purposes, it is best to declare a value of CND$5. If you
have questions, please contact the Committee Chair at
snoeyink@cs.ubc.ca or phone +1-604-822-8169.
NOTIFICATION: Authors will be notified of acceptance or rejection, and
given reviewer's comments by February 28, 1997. For each accepted
video, the final version of the textual description will be due by
March 16, 1997 for inclusion in the proceedings. Final versions of
accepted videos will be due May 1, 1997 in the best format available.
The accepted videos will be edited onto one tape, which will be shown
at the conference, distributed to the participants, and available from
ACM after the conference.
Video Program Committee:
Alain Fournier (University of British Columbia)
Mark Keil (University of Saskatchewan)
David Salesin (University of Washington)
Thomas C. Shermer (Simon Fraser University)
Jack Snoeyink (Chair; University of British Columbia)

: In article <55cc1m$dtr@news.jeack.com.au>, aj@axis.jeack.com.au (AJ) says:
: >
: >is there a formula that can be used to 
: >generate a sine wave that does not use the SIN function.
: >
: >i would like it to only use adds/subtracts/multiplys/divides.
: >
: >or any URL references where i might start looking.
: >
A digital oscillator can be constructed like this (c pseudocode):
  a = sin(2*pi*f); /* use a precomputed constant here */
  b = cos(2*pi*f); /* or sqrt(1-a*a) if you like */
  x = 0;
  y = 1;
  for (;;) {
	output(x, y);	/* x is a sine wave, y is a cosine */
	newx = b*x+a*y;
	newy = b*y-a*x;
	x = newx;
	y = newy;
  }
This is essentially a matrix multiply or a coordinate transform. You're
rotating a point about the origin by a fixed amount each step. The amount
depends on the original value of a.
	[ x', y' ] = [ x, y ] * | b, a |
				|-a, b |
Another way to look at it is that it's an infinite Q digital state variable
filter, or a state variable machine that solves the differential equation:
f'' + f = 0
---------------------------------------------------------------------------
	Kevin Morgan			|  Axiom of Infinity:
	San Jose, CA			!      An inductive (i.e. infinite)
	kmorgan@netcom.com  		|      set exists!
The only thing to do with good advice is pass it on.  It is never any
use to oneself.
		-- Oscar Wilde

a25467  wrote:
>Thanks, I need some help to make a university work about anything based in the
>linear resolution of matrix with an original !algoritmo! sorry but I am from
>spain .
>My work must be original (only a little) and i need some ideas 
>I am in the fourth course of maths and My teacher only told us to do something
>original for example :
>- in pascal or ...
>- new algoritms or a better solution to a theorem 
>Of couse I need !bibliografy!.
>Thanks and sorry for my english an for everything
>
I have written a math library for Turbo Pascal/Delphi. It is available
on my home page :
http://ourworld.compuserve.com/homepages/JDebord
This library includes a version of the Gauss-Jordan algorithm for
solving systems of linear equations, with some applications to linear
and nonlinear regression (not very original, however :)
For the bibliography I would recommend 'Numerical Recipes in Pascal'.
Note that their software can be improved in many ways, for instance by
using dynamic array allocation.
I hope this will be helpful.
Best regards,
Jean Debord
Limoges, France

I need to solve the system of linear equations
with matrix followed:
   A=I-alpha*d1*F*d2*F
where:
      I - unity matrix
      alpha - scalar(=2/N)
      d1 - diagonal matrix,(d1^-1 is singular matrix)
      F=sin(i*j*Pi/N); i,j=1...N
      d2 - diagonal matrix,(d2^-1 is singular matrix)
      N - dimension of system (large enough N=2^14)
 I've used  fft to compute y=A*x,and TFQMR algoritm.
Is there  more efficent way to solve Ax=b?
Matrix A can be rewriten as:
 A=I-d1*(T-H), where T=phi(|i-j|)-Toeplitz matrix
                     H=phi(i+j)  -Hankel matrix.
Any suggestions?
                      Dmitry Tikhonov
                      dimat@sunny.stack.net