Search   Memberlist   Usergroups
 Page 3 of 19 [276 Posts] View previous topic :: View next topic Goto page:  Previous  1, 2, 3, 4, 5, ..., 17, 18, 19 Next
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 pd-matrix ?

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
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.
Steve11
science forum beginner

Joined: 07 Feb 2005
Posts: 9

Posted: Thu Mar 24, 2005 7:28 pm    Post subject: Re: Flexible Floating-Point 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 floating-point offered on at least some architectures (i.e., the hexadecimal floating-point 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
non-existent 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
broad-spectrum 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
David W. Cantrell
science forum Guru

Joined: 02 May 2005
Posts: 352

Posted: Thu Mar 24, 2005 7:28 pm    Post subject: Re: Flexible Floating-Point 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
Peter Spellucci
science forum Guru

Joined: 29 Apr 2005
Posts: 702

Posted: Thu Mar 24, 2005 7:28 pm    Post subject: Re: convergence of QR-algorithm

In article <QuO%d.13\$it1.2@newsfe2-gui.ntli.net>,
"Jeremy Watts" <jwatts1970@hotmail.com> writes:
 Quote: "Bill Shortall" 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" wrote in message news:Woj%d.32203\$3A6.26295@newsfe1-gui.ntli.net... "hansm" 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 complex-conjugate 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
hansm

Joined: 24 Mar 2005
Posts: 97

 Posted: Thu Mar 24, 2005 7:28 pm    Post subject: Re: convergence of QR-algorithm 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 double-steps 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
John Savard
science forum beginner

Joined: 14 May 2005
Posts: 30

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

Steve Richfie1d <Steve@NOSPAM.smart-life.net> wrote in message news:<1110910906.bf168b09db3256f249d01177da071767@teranews>...

 Quote: Hey, you're stealing my thunder! Take a look at my kitchen sink proposal at 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 floating-point support package for a computer that will
receive a request that it provide floating-point computations which
satisfy certain properties, and which will meet that request using a
floating-point format supported by the underlying hardware if
possible, and will simulate a format in software with those properties
if necessary.

A hardware floating-point 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 floating-point offered on at least some
architectures (i.e., the hexadecimal floating-point of the IBM 360

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
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 QR-algorithm

 Quote: In article , "Jeremy Watts" writes: "hansm" 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 double-steps 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 Wilkinson-Shift 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
 Quote: hth peter
vonfeldt
science forum beginner

Joined: 24 Mar 2005
Posts: 1

 Posted: Thu Mar 24, 2005 7:28 pm    Post subject: Re: abstract algebra help please! see: http://math.berkeley.edu/~maschenb/113-fall-02/hw6.pdf problem 6b might be of interest...
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 QR-algorithm

"hansm" <mittelmann@asu.edu> wrote in message
 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 double-steps 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

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
>
Peter Spellucci
science forum Guru

Joined: 29 Apr 2005
Posts: 702

Posted: Thu Mar 24, 2005 7:28 pm    Post subject: Re: convergence of QR-algorithm

In article <zpv0e.169\$2j2.146@newsfe1-win.ntli.net>,
"Jeremy Watts" <jwatts1970@hotmail.com> writes:
 Quote: "hansm" 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 double-steps 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 Wilkinson-Shift 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
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 per-processor 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 dual-processor 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
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 QR-algorithm

"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" wrote in message news:Woj%d.32203\$3A6.26295@newsfe1-gui.ntli.net... "hansm" 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 complex-conjugate 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
Bill Shortall
science forum beginner

Joined: 14 Jun 2005
Posts: 11

Posted: Thu Mar 24, 2005 7:28 pm    Post subject: Re: convergence of QR-algorithm

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@newsfe1-gui.ntli.net...
 Quote: "hansm" 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 complex-conjugate 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
Everett M. Greene
science forum beginner

Joined: 09 Aug 2005
Posts: 32

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

Steve <Steve@NOSPAM.smart-life.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 broad-spectrum 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...

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 3 of 19 [276 Posts] Goto page:  Previous  1, 2, 3, 4, 5, ..., 17, 18, 19 Next View previous topic :: View next topic
 The time now is Fri Aug 17, 2018 6:12 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics how to deduce a number validation algorithm? Tim_Mac Math 1 Fri Jul 21, 2006 10:43 am uni. convergence bill1158 Math 3 Wed Jul 19, 2006 10:59 am convergence of probability measures pkg Math 0 Sat Jul 15, 2006 7:15 pm analysis with uniform convergence.. mina_world Math 4 Fri Jul 14, 2006 8:26 am Name of algorithm for pairwise comparison ? Paul Nutteing Math 10 Fri Jul 14, 2006 6:55 am