Author 
Message 
Peter Spellucci science forum Guru
Joined: 29 Apr 2005
Posts: 702

Posted: Thu Mar 24, 2005 7:28 pm Post subject:
Re: inversion of pdmatrix ?



In article <aek31at03odc@legacy>,
raaj_pmir@sify.com (Raj Kumar) writes:
Quote:  sir /mam
i am an student of master of personnel management and industrial
relations at Banaras Hindu University Varanasi India. i want to get
informatin about what in pd matrix, why is it their in industries, how
is is done.

any type of minimization problem involving several variables finally ends up
with dealing with linear equations with a pd matrix, for example.
hth
peter 

Back to top 


Paul1133 science forum beginner
Joined: 24 Mar 2005
Posts: 5

Posted: Thu Mar 24, 2005 7:28 pm Post subject:
Re: I need help in writing a recursion formula for a series.



On 17 Oct 04 00:23:07 0400 (EDT), alethia wrote:
Quote:  a = 1
n / n
2
Please help, I do not understand how to write this formula into a
recrusion formula. Thank you

Must be a virus since I caught this problem also. 

Back to top 


Steve11 science forum beginner
Joined: 07 Feb 2005
Posts: 9

Posted: Thu Mar 24, 2005 7:28 pm Post subject:
Re: Flexible FloatingPoint Standard Proposal



John,
Quote:  This is an interesting idea. Why is the committee dealing with IEEE
754 ignoring it?

NIH = Not Invented Here. About a decade ago I was approached to
coordinatge the IEEE FP effort, My response "GREAT, now I fan fix all of
the problems it has!" "What Problems?" The next half hour was taken up
with my explanation of its many problems. That was the end of THAT
discussion. I probably should have just kept quiet until I had the position.
Quote:  There is actually a simple reason. Although an interesting idea, it
would require effort to implement. Thus, the fact that it exists as an
alternative is not enough to lead to an effort to standardize it.
The effort to create IEEE 754 resulted from a groundswell of demand
among people using computers to perform numerical calculations, based
on the fact that the floatingpoint offered on at least some
architectures (i.e., the hexadecimal floatingpoint of the IBM 360
series) was inadequate, and that gradual underflow was sorely needed.
Some items, such as affine infinity, were dropped from IEEE 754  they
were implemented on the 8087, but not on its successors, therefore.
If enough people who work with numbers think that something like your
proposal is needed, then, once they take it up, this idea *will* go
somewhere; but there has to be a real demand before it is felt that it
is worth the effort.

Here is the problem. Global Warming, outsourcing, the balance of trade,
etc., are all things that are now being allowed because present
simulations completely and hopelessly fail to predict their effects.
Further, there is good reason that these fixes to FP would make much
more reliable simulations possible. However, the people doing this don't
represent 1% of the PC users. Seeing some of the logical traps that the
VERY competent people on this forum fall into (e.g. using algorithms
that don't preserve significance/dimensionality) and complain about
nonexistent problems, what chance is there for the community of users
to ever understand these issues.
Indeed, much of the present '754 is via "proof by authority" of the
person now commonly referred to as the "Father of IEEE FP", when in fact
even HE lacked the skills to do a good job of this, to the point of
leaving no smooth path for extension.
As I see it, the fundamental process is broken with little prospect for
broadspectrum repair. Even PhD /Math people lack the skills needed to
participate usefully in this discussion. The ONLY hope I see is for some
competent person in Sun or Intel to "see the light" and run with this.
Steve Richfie1d 

Back to top 


David W. Cantrell science forum Guru
Joined: 02 May 2005
Posts: 352

Posted: Thu Mar 24, 2005 7:28 pm Post subject:
Re: Flexible FloatingPoint Standard Proposal (was: Decimal ... JOSS)



jsavard@ecn.ab.ca (John Savard) wrote:
[snip]
Quote:  Some items, such as affine infinity, were dropped from IEEE 754  they
were implemented on the 8087, but not on its successors, therefore.

FWIW:
I think you meant to say that the projective infinity was dropped. The
affine infinities were retained in IEEE 754.
David 

Back to top 


Peter Spellucci science forum Guru
Joined: 29 Apr 2005
Posts: 702

Posted: Thu Mar 24, 2005 7:28 pm Post subject:
Re: convergence of QRalgorithm



In article <QuO%d.13$it1.2@newsfe2gui.ntli.net>,
"Jeremy Watts" <jwatts1970@hotmail.com> writes:
Quote: 
"Bill Shortall" <pecos@cminet.net> wrote in message
news:d1nan8027pp@enews3.newsguy.com...
Hi Jeremy,
I assume you are working with a general real non symmetric or non
hermitian matrix and have reduced it to
upper hessenburg form.
Bill, yes I'm doing all of that., alongside using a shift that is the
element in the bottom right hand corner of the matrix of the current matrix
being worked upon.
Consider the
2x2 matrix in the lower right corner. calculate the eigenvalues of this.
If
they are complex do a qr iteration twice using first one eigenvalue then
it's conjugate. as the shift If they are real use one after the other as
a
shift. In either case the bottom two elements below the diagonal should
slowly disappear. Forget about what happens in the upper left corner
defate from the bottomDo all calculations in complex form completely.
Double
check your QR decomposition make sure everything works in complex. This
way
is very slow but it is easier to understand than the francis method.
I had a look at Francis's method and likely think it would be slower than
the one I'm using as it involves more calculation at each iteration. Unless
of course it involves fewer iterations. But my scheme isnt bad and usually
finds an eigenvalue after less than 10 iterations.
What I've done now is to use QR with shifts, and check for convergence in
the top or bottom of the diagonal (bottom invariably converges first but not
always), and then deflate the matrix as I explained in my original post. If
for a matrix which does not fully converge, then of the ones I have tested,
it does seem the case that the final two eigenvalues are left in this 2x2
block that does not converge.
So I have got my program to use Cramers rule on this block to retrieve the
final two and then use inverse iteration to hone them down completely. The
only problem I can see with this is if two bulges ever develop in a matrix 
one say near the top of the diagonal and the other at the bottom. In this
case convergence could never occur. Do you think this could ever happen?
Also would you say that using eigenvalues of the last 2x2 block as shifts
would be faster than my current scheme which simply uses the last element of
the diagonal?
nonconvergence of QR can occur if there are eigenvalues of same absolute value 
which are different. ths is what hans did write already. this can occur without
shifts or after an unhappy shift. this is the reason why QR codes check for
convergence after a predefined number of steps and in case of nonconvergence
use "exception shifts" (which have nothing to do with your Rayleigh Shift
or the Wilkinson shift. at least for symmetric matrices it is clear that the
Wilkinson shift based on the right lower 2 by 2 matrix is faster than the
Rayleigh Shift.) since complex arithmetic has four times the cost of real
arithmetic, for real matrices the Francis double shift is indeed cheaper.
(if not special hardware is present which allows parallelization of the
multiplies in complex arithmetic)
but of course doing it all in complex arithmetic is simpler and also a random
complex shift will almost for sure break any set of eigenvalues of equal modulus and
hence enforce convergence.
hth
peter
Quote:  thanks
regards...bill shortall .. pecos_place()
"Jeremy Watts" <jwatts1970@hotmail.com> wrote in message
news:Woj%d.32203$3A6.26295@newsfe1gui.ntli.net...
"hansm" <mittelmann@asu.edu> wrote in message
news:1111341866.314472.120360@g14g2000cwa.googlegroups.com...
Hi,
I strongly suggest you consult a good boock on numerical algebra and
study the QR algorithm. Things are much more complicated. If you work
in real arithmetic for complexconjugate eigenvalues only a 2x2 block
will converge. However, if you have real deficient eigenvalues then
even a larger block will only converge. To make QR work and also be
efficient you have to apply a variety of measures such as initial
reduction to Hessenberg form, single/double shifts etc.
Books are Demmel, Golub&VanLoan etc
Hans Mittelmann
Hello Hans,
Yes I am working with complex arithmetic, and also reducing the matrix to
Hessenberg form as a first step. I also add a 'complex shift' to the
diagonal of the matrix if it is real, as this seems to ensure that the
complex eigenvalues appear if there are any.
Jeremy



Back to top 


hansm science forum addict
Joined: 24 Mar 2005
Posts: 97

Posted: Thu Mar 24, 2005 7:28 pm Post subject:
Re: convergence of QRalgorithm



Hi,
you say you need "usually less than 10 iterations" per eigenvalue. For
general real matrices with the Francis shift you need on average 1.5 of
these doublesteps and with alternative single shifts in case of
convergence to real eigenvalues you can speed it up some more etc etc.
But your goal is more simplicity of the program and robustness and not
absolute efficiency.
Hans Mittelmann 

Back to top 


John Savard science forum beginner
Joined: 14 May 2005
Posts: 30

Posted: Thu Mar 24, 2005 7:28 pm Post subject:
Flexible FloatingPoint Standard Proposal (was: Decimal ... JOSS)



Steve Richfie1d <Steve@NOSPAM.smartlife.net> wrote in message news:<1110910906.bf168b09db3256f249d01177da071767@teranews>...
Quote:  Hey, you're stealing my thunder! Take a look at my kitchen sink proposal
at <http://www.smartlife.net/FP> Perhaps we should be borrowing from
each other's kitchen sinks?!

Looking at your web page further, I see that what you appear to be
proposing is a standard for the following:
A software floatingpoint support package for a computer that will
receive a request that it provide floatingpoint computations which
satisfy certain properties, and which will meet that request using a
floatingpoint format supported by the underlying hardware if
possible, and will simulate a format in software with those properties
if necessary.
A hardware floatingpoint coprocessor could also implement this as a
standard.
This is an interesting idea. Why is the committee dealing with IEEE
754 ignoring it?
There is actually a simple reason. Although an interesting idea, it
would require effort to implement. Thus, the fact that it exists as an
alternative is not enough to lead to an effort to standardize it.
The effort to create IEEE 754 resulted from a groundswell of demand
among people using computers to perform numerical calculations, based
on the fact that the floatingpoint offered on at least some
architectures (i.e., the hexadecimal floatingpoint of the IBM 360
series) was inadequate, and that gradual underflow was sorely needed.
Some items, such as affine infinity, were dropped from IEEE 754  they
were implemented on the 8087, but not on its successors, therefore.
If enough people who work with numbers think that something like your
proposal is needed, then, once they take it up, this idea *will* go
somewhere; but there has to be a real demand before it is felt that it
is worth the effort.
John Savard 

Back to top 


Jeremy Watts science forum Guru Wannabe
Joined: 24 Mar 2005
Posts: 239

Posted: Thu Mar 24, 2005 7:28 pm Post subject:
Re: convergence of QRalgorithm



"Peter Spellucci" <spellucci@fb04373.mathematik.tudarmstadt.de> wrote in
message news:d1unqm$r9k$1@fb04373.mathematik.tudarmstadt.de...
Quote: 
In article <zpv0e.169$2j2.146@newsfe1win.ntli.net>,
"Jeremy Watts" <jwatts1970@hotmail.com> writes:
"hansm" <mittelmann@asu.edu> wrote in message
news:1111620492.270399.261940@o13g2000cwo.googlegroups.com...
Hi,
you say you need "usually less than 10 iterations" per eigenvalue. For
general real matrices with the Francis shift you need on average 1.5 of
these doublesteps and with alternative single shifts in case of
convergence to real eigenvalues you can speed it up some more etc etc.
But your goal is more simplicity of the program and robustness and not
absolute efficiency.
Hans Mittelmann
Hans,
Yes I've had a look at the Francis method and it seems to be the method
of
choice for eigenvalue finding, but it seems to require a real matrix.
Mine
may be complex too. Can the method be modified to work with complex
matrices too? My routines to find Householder matrices/reflections can
already cope with complex vectors.
The method I am currently using is to firstly decompose to Hessenberg
form,
then to use a shift given by the last element in the diagonal (Rayleigh
shift I think this is called), but as I've said, this on occasion can
fail
to fully converge, and can be slow (but much faster than using no
shifts).
I may try using a Wilkinson shift to see if that solves the convergence
failure problem. Is QR with a Wilkinson shift faster than QR with a
Rayleigh shift do you know?
Jeremy
the Francis double shift is meant for avoiding complex arithmetic on a
real
matrix if one uses the wilkinson shift to break a pair of eigenvalues of
equal
modulus. for a complex matrix it makes no sense.
yes, QR with WilkinsonShift is in general faster than the Rayleighshift,
but the proof of cubic/supercubic convergence (see Parlett) works
for the hermitian case only as far as I know

Peter,
I came across something that says in the event of a convergence failure,
then the use of an 'ad hoc' shift can be used to attempt convergence. It
doesnt however say anything further. Does an 'ad hoc' shift mean a random
shift?
Jeremy


Back to top 


vonfeldt science forum beginner
Joined: 24 Mar 2005
Posts: 1


Back to top 


Jeremy Watts science forum Guru Wannabe
Joined: 24 Mar 2005
Posts: 239

Posted: Thu Mar 24, 2005 7:28 pm Post subject:
Re: convergence of QRalgorithm



"hansm" <mittelmann@asu.edu> wrote in message
news:1111620492.270399.261940@o13g2000cwo.googlegroups.com...
Quote:  Hi,
you say you need "usually less than 10 iterations" per eigenvalue. For
general real matrices with the Francis shift you need on average 1.5 of
these doublesteps and with alternative single shifts in case of
convergence to real eigenvalues you can speed it up some more etc etc.
But your goal is more simplicity of the program and robustness and not
absolute efficiency.
Hans Mittelmann

Hans,
Yes I've had a look at the Francis method and it seems to be the method of
choice for eigenvalue finding, but it seems to require a real matrix. Mine
may be complex too. Can the method be modified to work with complex
matrices too? My routines to find Householder matrices/reflections can
already cope with complex vectors.
The method I am currently using is to firstly decompose to Hessenberg form,
then to use a shift given by the last element in the diagonal (Rayleigh
shift I think this is called), but as I've said, this on occasion can fail
to fully converge, and can be slow (but much faster than using no shifts).
I may try using a Wilkinson shift to see if that solves the convergence
failure problem. Is QR with a Wilkinson shift faster than QR with a
Rayleigh shift do you know?
Jeremy
> 

Back to top 


Peter Spellucci science forum Guru
Joined: 29 Apr 2005
Posts: 702

Posted: Thu Mar 24, 2005 7:28 pm Post subject:
Re: convergence of QRalgorithm



In article <zpv0e.169$2j2.146@newsfe1win.ntli.net>,
"Jeremy Watts" <jwatts1970@hotmail.com> writes:
Quote: 
"hansm" <mittelmann@asu.edu> wrote in message
news:1111620492.270399.261940@o13g2000cwo.googlegroups.com...
Hi,
you say you need "usually less than 10 iterations" per eigenvalue. For
general real matrices with the Francis shift you need on average 1.5 of
these doublesteps and with alternative single shifts in case of
convergence to real eigenvalues you can speed it up some more etc etc.
But your goal is more simplicity of the program and robustness and not
absolute efficiency.
Hans Mittelmann
Hans,
Yes I've had a look at the Francis method and it seems to be the method of
choice for eigenvalue finding, but it seems to require a real matrix. Mine
may be complex too. Can the method be modified to work with complex
matrices too? My routines to find Householder matrices/reflections can
already cope with complex vectors.
The method I am currently using is to firstly decompose to Hessenberg form,
then to use a shift given by the last element in the diagonal (Rayleigh
shift I think this is called), but as I've said, this on occasion can fail
to fully converge, and can be slow (but much faster than using no shifts).
I may try using a Wilkinson shift to see if that solves the convergence
failure problem. Is QR with a Wilkinson shift faster than QR with a
Rayleigh shift do you know?
Jeremy

the Francis double shift is meant for avoiding complex arithmetic on a real
matrix if one uses the wilkinson shift to break a pair of eigenvalues of equal
modulus. for a complex matrix it makes no sense.
yes, QR with WilkinsonShift is in general faster than the Rayleighshift,
but the proof of cubic/supercubic convergence (see Parlett) works
for the hermitian case only as far as I know
hth
peter 

Back to top 


Hiu Chung Law science forum beginner
Joined: 03 May 2005
Posts: 18

Posted: Thu Mar 24, 2005 7:28 pm Post subject:
Re: (Epsilon OT) Weird Intel FP performance variation



Phil Hobbs <pcdh@spammesenseless.us.ibm.com> wrote:
Quote:  I have a large electromagnetic simulator based on the FDTD (finite
difference, time domain) algorithm. It attempts to get a performance
boost by precomputing a strategy, and then carrying it out many times,
so its inner loop traverses a linked list of maybe 100k rows of voxels,
with each voxel in the row containing the same material. This seems to
optimize much better than the usual approach, which is to put a big
switch statement inside 3 nested loops iterating over the whole
simulation domain. The gain is about 30% average on a perprocessor
basis, which I'm very happy with.
I notice one very weird thing: with a localized source, the simulation
runs very fast at the start, gradually slows down by a factor of as much
as 10 for awhile, and then rapidly speeds back up again, continuing fast
until it's completed. The CPU usage stays at 100% the entire time. It
looks as though something slow is happening as the domain goes from all
0.0 to finite values, but I don't know what. This is especially
noticeable on a dualprocessor Xeon machine running the simulation on
several threads, but it happens on a PIII running all the work on one
thread.
A factor of 10 is a serious thing, seriously denting the performance
gain I've been working for. I don't know enough about the inner
workings of the Intel FPU to understand it, but if I'm right, it's
connected with the presence of a lot of very small nonzero FP values.
Any ideas about what's going on?

Quote:  Thanks,
Phil Hobbs
IBM T. J. Watson Research Center

You may want to repeat the above using an AMD processor. AMD processor
is much faster than Pentium when NaN, Inf and denormal are encountered.
If such phenomenon disappears for AMD, we know for sure that it
is the weird FP design in Pentium causing the trouble. 

Back to top 


Jeremy Watts science forum Guru Wannabe
Joined: 24 Mar 2005
Posts: 239

Posted: Thu Mar 24, 2005 7:28 pm Post subject:
Re: convergence of QRalgorithm



"Bill Shortall" <pecos@cminet.net> wrote in message
news:d1nan8027pp@enews3.newsguy.com...
Quote:  Hi Jeremy,
I assume you are working with a general real non symmetric or non
hermitian matrix and have reduced it to
upper hessenburg form.

Bill, yes I'm doing all of that., alongside using a shift that is the
element in the bottom right hand corner of the matrix of the current matrix
being worked upon.
Consider the
Quote:  2x2 matrix in the lower right corner. calculate the eigenvalues of this.
If
they are complex do a qr iteration twice using first one eigenvalue then
it's conjugate. as the shift If they are real use one after the other as
a
shift. In either case the bottom two elements below the diagonal should
slowly disappear. Forget about what happens in the upper left corner
defate from the bottomDo all calculations in complex form completely.
Double
check your QR decomposition make sure everything works in complex. This
way
is very slow but it is easier to understand than the francis method.

I had a look at Francis's method and likely think it would be slower than
the one I'm using as it involves more calculation at each iteration. Unless
of course it involves fewer iterations. But my scheme isnt bad and usually
finds an eigenvalue after less than 10 iterations.
What I've done now is to use QR with shifts, and check for convergence in
the top or bottom of the diagonal (bottom invariably converges first but not
always), and then deflate the matrix as I explained in my original post. If
for a matrix which does not fully converge, then of the ones I have tested,
it does seem the case that the final two eigenvalues are left in this 2x2
block that does not converge.
So I have got my program to use Cramers rule on this block to retrieve the
final two and then use inverse iteration to hone them down completely. The
only problem I can see with this is if two bulges ever develop in a matrix 
one say near the top of the diagonal and the other at the bottom. In this
case convergence could never occur. Do you think this could ever happen?
Also would you say that using eigenvalues of the last 2x2 block as shifts
would be faster than my current scheme which simply uses the last element of
the diagonal?
thanks
Quote: 
regards...bill shortall .. pecos_place()
"Jeremy Watts" <jwatts1970@hotmail.com> wrote in message
news:Woj%d.32203$3A6.26295@newsfe1gui.ntli.net...
"hansm" <mittelmann@asu.edu> wrote in message
news:1111341866.314472.120360@g14g2000cwa.googlegroups.com...
Hi,
I strongly suggest you consult a good boock on numerical algebra and
study the QR algorithm. Things are much more complicated. If you work
in real arithmetic for complexconjugate eigenvalues only a 2x2 block
will converge. However, if you have real deficient eigenvalues then
even a larger block will only converge. To make QR work and also be
efficient you have to apply a variety of measures such as initial
reduction to Hessenberg form, single/double shifts etc.
Books are Demmel, Golub&VanLoan etc
Hans Mittelmann
Hello Hans,
Yes I am working with complex arithmetic, and also reducing the matrix to
Hessenberg form as a first step. I also add a 'complex shift' to the
diagonal of the matrix if it is real, as this seems to ensure that the
complex eigenvalues appear if there are any.
Jeremy



Back to top 


Bill Shortall science forum beginner
Joined: 14 Jun 2005
Posts: 11

Posted: Thu Mar 24, 2005 7:28 pm Post subject:
Re: convergence of QRalgorithm



Hi Jeremy,
I assume you are working with a general real non symmetric or non
hermitian matrix and have reduced it to
upper hessenburg form. Consider the
2x2 matrix in the lower right corner. calculate the eigenvalues of this. If
they are complex do a qr iteration twice using first one eigenvalue then
it's conjugate. as the shift If they are real use one after the other as a
shift. In either case the bottom two elements below the diagonal should
slowly disappear. Forget about what happens in the upper left corner
defate from the bottomDo all calculations in complex form completely. Double
check your QR decomposition make sure everything works in complex. This way
is very slow but it is easier to understand than the francis method.
regards...bill shortall .. pecos_place()
"Jeremy Watts" <jwatts1970@hotmail.com> wrote in message
news:Woj%d.32203$3A6.26295@newsfe1gui.ntli.net...
Quote: 
"hansm" <mittelmann@asu.edu> wrote in message
news:1111341866.314472.120360@g14g2000cwa.googlegroups.com...
Hi,
I strongly suggest you consult a good boock on numerical algebra and
study the QR algorithm. Things are much more complicated. If you work
in real arithmetic for complexconjugate eigenvalues only a 2x2 block
will converge. However, if you have real deficient eigenvalues then
even a larger block will only converge. To make QR work and also be
efficient you have to apply a variety of measures such as initial
reduction to Hessenberg form, single/double shifts etc.
Books are Demmel, Golub&VanLoan etc
Hans Mittelmann
Hello Hans,
Yes I am working with complex arithmetic, and also reducing the matrix to
Hessenberg form as a first step. I also add a 'complex shift' to the
diagonal of the matrix if it is real, as this seems to ensure that the
complex eigenvalues appear if there are any.
Jeremy



Back to top 


Everett M. Greene science forum beginner
Joined: 09 Aug 2005
Posts: 32

Posted: Thu Mar 24, 2005 7:28 pm Post subject:
Re: Flexible FloatingPoint Standard Proposal



Steve <Steve@NOSPAM.smartlife.net> writes:
Quote: 
This is an interesting idea. Why is the committee dealing with IEEE
754 ignoring it?
NIH = Not Invented Here. About a decade ago I was approached to
coordinatge the IEEE FP effort, My response "GREAT, now I fan fix all of
the problems it has!" "What Problems?" The next half hour was taken up
with my explanation of its many problems. That was the end of THAT
discussion. I probably should have just kept quiet until I had the position.
[snip]
Indeed, much of the present '754 is via "proof by authority" of the
person now commonly referred to as the "Father of IEEE FP", when in fact
even HE lacked the skills to do a good job of this, to the point of
leaving no smooth path for extension.
As I see it, the fundamental process is broken with little prospect for
broadspectrum repair. Even PhD /Math people lack the skills needed to
participate usefully in this discussion. The ONLY hope I see is for some
competent person in Sun or Intel to "see the light" and run with this.

How about enlightening the great unwashed masses as to
the nature of the deficiencies?
Of course, this may be difficult since you say that there
is almost nobody (besides you) who can understand the issues... 

Back to top 


Google


Back to top 



The time now is Tue Apr 24, 2018 4:48 am  All times are GMT

