Re: time complexity for iterative methods
- From: Nimo <azeez541@xxxxxxxxx>
- Date: Sat, 18 Apr 2009 22:13:10 -0700 (PDT)
On Apr 18, 8:36 am, spellu...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
(Peter Spellucci) wrote:
In article <aafcf624-c7c7-408a-86b2-673b22e96...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Nimo <azeez...@xxxxxxxxx> writes:
On Apr 17, 6:39=A0am, spellu...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
(Peter Spellucci) wrote:
In article <6bb2cf33-e7d4-488e-9be7-af4bc8f87...@xxxxxxxxxxxxxxxxxxxxxxxx=com>,
=A0Nimo <azeez...@xxxxxxxxx> writes:
Hi..,
well, the question might not be exact to the point
because it depends mostly upon the
nature of the Matrix {sparse,symmetric, positive definite..etc..}
Problem =A0 =A0 =A0:- =A0solving A x =3D3D B
Tool applied :- Iterative methods
Doubt on =A0 =A0 :- Time complexity { linear or loglinear..etc..}
coming to the precision,
a good enough precision {upto 5-7digits} is enough
I don't want super-duper precise values.
so the 2 cases are
(a) General; A x =3D3D B
(b) sparse, positive definite + symmetric; A x =3D3D B
in the above both cases for a N x N matrix;
{ default: N =3D3D 1million }
Is it possible for linear solvers ?
at least I'm expecting for case(b)
=A0 =A0...to apply..it...!
any suggestions/ideas/web-links too
thnx a lot for the help :)
=A0n=3D10^6 , A (truly) "general" : forget it.
=A0what is applicable:
=A0GMRES with complete reorthogonalization,
=A0Kaczmarc.
=A0GMRES "restartet" will fail in general (I have examples where this is =the case
=A0even for n=3D100. eigenvalue distribution starlike around zero, wellco=nditioned)
=A0GMRES "full" with reorthogonalization requires more effort than LU,
=A0LU (full) : (2/3)*n^3 =A0 .. forget it
=A0Kaczmarc: converges always, but error reduction is abouturacy just produced.
=A01-1/(constant*cond(A))
=A0hence too slow and accumulated roundoff errors may spoil increased acc=
=A0so lets go to the better case:
=A0something sparse, symmetric positive definite or at least the symmetri=c part
=A0positive definite. then CG (pos. def. symm) or GMRES or QMR or similar=things
=A0come into mind. again here the error reduction depends on the conditio=n number
=A0at least as the step number is considerably less than n, as we will ho=pe.
=A0(yes, cg and full GMRES are finite, theoretically, but we will hope no=t
=A0 to use 10^6 steps)y
=A0hence you might hope for something like
=A01-const/sqrt(cond(A)) =A0
=A0as the error reduction for a single step.
=A0often cond(A)=3DO(n^2) =A0
=A0and then , finally, you are in a position to assess the time complexit=
=A0knowing the effort for the matrix vector product,stant
=A0and the required precision, and hopefully with some idea about the con=
=A0behind O(.).
=A0And clearly, the necessity of preconditioning becomes obvious.
=A0hth
=A0peter
________
uuhhh...
when I first posted my thread in num-analysis upon this doubt,
may be 3months back
Handebrujin had suggested me SOR for N=3D 10^9; and guaranteed that
it will be linear ....
which is correct. convergence of SOR for pos def symm is linear, but
in the best known case, namely a consistently ordered symmetric positive
definite matrix with diagonal all ones it is
1-const/(sqrt(cond(A))+1)
hence you might imagine how much it will take, if cond(A)=O(n^2)
and n=10^6, to reach your desired 7 digits precision
wow...then, it would be cakewalk for me to accomplish my job,
I've to adjust my matrix for this specifications;
I hope with a little bit of homework,
I can modify my data for this matrix.If I got any doubts
I'll come to you...in the mean-time have a nice weekend :)
____
Fifty years of intense reflection have not brought
me nearer to the answer of the question
=> ‘What are light quanta?’
Of course nowadays every little mind thinks he knows
the answer. But he is wrong.He said this a few years
before his death
Albert Einstein, 1951
Any how we will stop this here...., and
=3D> I want to clarify my self a small doubt regarding A x =3D B
My_statement =3D> from mathematical point of view,
we will find un-known co-effs
to minimize residual and get a meaningful
equation as an end result
=3D> From CAD point of view why you people find un-known co-effs ?
why do you do that ? what's the use with it ?
to support my statement I'm directly providing Google book result
see here
http://books.google.co.in/books?id=3DcpP_K9wK_dIC&pg=3DPP14&lpg=3DPP1...
=3DNumerical+Solution+of+Partial+Differential+Equations+in+Science+and+Engi=
neering&output=3Dhtml
sub-topic { 4.12 }
I'm very eager to know, for CAD
" why A x =3D B is the backbone "
___________
because, in order to find a smooth curve or surface for given discrete
data, you will have to solve large or even hugh linear systems.
hth
peter
To speak of non-linear physics is like calling
zoology the study of non-elephant animals.
Stanislaw Ulam
.
- Follow-Ups:
- Re: time complexity for iterative methods
- From: Bruce Scott TOK
- Re: time complexity for iterative methods
- References:
- time complexity for iterative methods
- From: Nimo
- Re: time complexity for iterative methods
- From: Peter Spellucci
- Re: time complexity for iterative methods
- From: Nimo
- Re: time complexity for iterative methods
- From: Peter Spellucci
- time complexity for iterative methods
- Prev by Date: Re: Curve Fitting and building an equation
- Next by Date: Re: Curve Fitting and building an equation
- Previous by thread: Re: time complexity for iterative methods
- Next by thread: Re: time complexity for iterative methods
- Index(es):
Relevant Pages
|
