Re: Matrix decomposition, time complexity doubt?

On 2009-02-06 00:40:20 -0400, Nimo <azeez541@xxxxxxxxx> said:

On Feb 6, 12:50 am, Gordon Sande <g.sa...@xxxxxxxxxxxxxxxx> wrote:
On 2009-02-05 15:20:07 -0400, Nimo <azeez...@xxxxxxxxx> said:

Hi,

A (u) = F

To decompose a sparse, symmetric & positive definite
matrix (A), with number of co-efficients (column vector)
to find (u) are up to 10^6 + 1,00,000.
a) How much time (in seconds) it would take ?
b) what method would would you advise ?
(considering that all the co-efficients should be
exact values)

By exact do you mean that the result is a many digit rational number
or that the result is a finite precision (i.e. floating point) evaluation
of a correct algebraic formulae instead of an iterative approximation?

The rational arithmetic is usually called symbolic evaluation and is rather
slower than floating point.

10^6 exact (i.e. symbolic) values would seem to be a curious sort of problem
for other than comninatorics. Can you provide more information?

Timings for sparse problems depend on the form of the sparsity. More
information
would be needed to provide any even wild guesses of timings.

Thank_you :)



_____ PART - ii___See below for PART - i______

Let A u = f

I have to find the column vector( u) which has
no.of unknowns are 1,000,000,000 = 10^9

__ __
| u1 |
| u2 |
| u3 |
| u4 |
| u5 |
A | u6 | = f
| . |
| . |
| . |
| . |
| . |
|__ N=10^9__|

Where no.of unknowns of u(1,2,.... N ) = 10^9 terms

considering that A is sparse, symmetric & positive definite;
I've to find out the exact values, not iterations or approximations.

1) how much time(in seconds) it would take on a desktop PC?

At 8 bytes for each of the un's you need 8 GigaBytes which is
possible but large for a desktop PC.

If 10^9 is too much, then consider 10^7 instead of 10^9.
tell me the complexity & how much time(in seconds) it would take?

Wikipedia article stated that, for hundred thousand terms (1,00,000)

Sparse LU or
Cholesky LU ; is very much enough
but it doesn't provide me details about how much time it would take ?
and it also suggested that for symmetric & Positive definite
matrices I should go for "conjugate gradient" method,
but I think that method is just approximation, but not
produce exact values.

__________PART-i________________

I'm giving you my exact problem,
Please,help me with any suggestion/idea.

Problem:
Finding out the kernel 'k(x,t)' for the
given Integral equation subject to the
provided conditions.

Int 0_N Int 0_N k(x,t) dx dt = a
Int 0_N Int 0_N-1 k(x,t) dx dt = b
Int 0_N Int 0_N-2 k(x,t) dx dt = c
Int 0_N Int 0_N-3 k(x,t) dx dt = d
.
.
.
.
.
.
.
.
Int 0_N Int 0_1 k(x,t) dx dt = p

So there will be 10^9 rows with about ( 10^9 )^2
entries (mere factors of 10 don't matter here!).
Your desktop PC will not have this much memory.
Any disk would wear out from paging if you were to
use a virtual memory at these sizes. And the disk
would be rather large as well.

(such that N is up to 10^7-to-10^9 or so)

Solution technique: I'm opting
Tool: Galerkin approach

I'm approximating the kernel with the
help of Galerkin method
http://en.wikipedia.org/wiki/Galerkin_method

At the end I'll end up with system of
linear equations in the form A u = f {from here see PART -ii}

I hope you've understood my problem now.

Doubts:-

1)For normal procedure(Galerkin method)
I know how to take the values in the matrix A.

but, here right hand side values of the equation is
given, I'm a bit confusing how to take values.

2) More over if I go with iterations for solution,
I'll not get balanced with values of Integral
on the right hand side, so I'm looking
exact values. that's why I asked here
which method to implement for solving the matrix.

If you know any other technique besides this
to solve this type of Integral equation,

please advise me with it, considering that
I've to cope with Time complexity & large N value.

Thank_you
any more?
please ask it.

I expect that you need to find a local computer scientist/numerical
analyst who can fill you in on all the background that you appear to
be missing. The form of the questions, citing Wiki as your main references
etc leave the impression that you need much more extensive advice than
you will ever get through newsgroups.

Maybe you should try with 10^2 variables to see what yuu can learn from
doing the toy example before trying bigger things. And even the toy problem
will need help from your local expert.




.

Relevant Pages

  • Re: Matrix decomposition, time complexity doubt?
    ... By exact do you mean that the result is a many digit rational number ... of a correct algebraic formulae instead of an iterative approximation? ... Int 0_N Int 0_N kdx dt = a ... to solve this type of Integral equation, ...
    (sci.math.num-analysis)
  • Re: On writing negative zero - with or without sign
    ... of representing an "exact" zero... ... My definition of an "exact" zero is whatever internal representation ... *only* value associated with that approximation. ... A subset of floating point numbers can have an exact representation. ...
    (comp.lang.fortran)
  • Re: Visualization of unmeasurable sets and computability
    ... it does not have to be exact! ... rough approximation of the postivie-measure Cantor set: ... So then a "rough visualization" achieved by spitting out ... Does non-measurability of a set imply that no algorithm can ...
    (sci.math)
  • Re: The spinoza papers: design of the extra-precision number object 2
    ... approximation will be truncated to some arbitrary point (either a fixed ... But many "real" values are also exact. ... measuring, there comes a point (which varies depending on what we're ...
    (comp.programming)
  • Re: relating controls to hcp
    ... [regarding exact values versus sims] ... >>>From hcp in the range 5 to 29, the best fit line for expected controls ... An approximation A * hcp - B cannot be accurate to two decimals. ... > the exact figures, to 2 dp, are shown below. ...
    (rec.games.bridge)