Singular Value Decomposition (SVD) Ada Algorithm

Singular Value Decomposition (SVD) Ada Algorithm

[skidmarks]

Anyone have an SVD in Ada? I have the C/C++ versions from Numerical
Recipes in C++ (I have the CD-ROM) and would rather not rewrite it
into Ada unless I have to.

art

Re: Singular Value Decomposition (SVD) Ada Algorithm

[Jeffrey Carter]

skidmarks wrote:

> Anyone have an SVD in Ada? I have the C/C++ versions from Numerical
> Recipes in C++ (I have the CD-ROM) and would rather not rewrite it
> into Ada unless I have to.

I'm sure these exist; check adapower.com and adaworld.com.

The PragmAda Reusable Components do not offer SVD, but do provide QR 
factorization, if that is of interest:

http://home.earthlink.net/~jrcarter010/pragmarc.htm

-- 
Jeff Carter
"Every sperm is sacred."
Monty Python's the Meaning of Life
55

Re: Singular Value Decomposition (SVD) Ada Algorithm

[John Woodruff]

aschwarz@acm.org (skidmarks) wrote in message news:<35f054ea.0410290918.5f7f7d0@posting.google.com>...
> Anyone have an SVD in Ada? I have the C/C++ versions from Numerical
> Recipes in C++ (I have the CD-ROM) and would rather not rewrite it
> into Ada unless I have to.
> 
> art

I have a considerable collection of publicly available Ada libraries,
and I find that there is one that defines an SVD:

You can acquire the Drexel U Matrix Math items from  
http://dflwww.ece.drexel.edu/research/ada/
They are marked:
-- Copyright (c) Drexel University, 1996                       --
-- Data Fusion Laboratory                                      --
-- Electrical and Computer Engineering Department              --
-- $AUTHORS: Chris Papademetrious, Xiaoxun Zhu, Moshe Kam

Their package  Generic_Real_Arrays.Operations defines a subprogram
"Singular_Value_Decomposition".

This might be what you want!

John

Re: Singular Value Decomposition (SVD) Ada Algorithm

[skidmarks]

> 
> I have a considerable collection of publicly available Ada libraries,
> and I find that there is one that defines an SVD:
> 
> You can acquire the Drexel U Matrix Math items from  
> http://dflwww.ece.drexel.edu/research/ada/
> They are marked:
> -- Copyright (c) Drexel University, 1996                       --
> -- Data Fusion Laboratory                                      --
> -- Electrical and Computer Engineering Department              --
> -- $AUTHORS: Chris Papademetrious, Xiaoxun Zhu, Moshe Kam
> 
> Their package  Generic_Real_Arrays.Operations defines a subprogram
> "Singular_Value_Decomposition".
> 
> This might be what you want!

Thank you. I haven't looked closely but have looked enough (to say) it
seems to be what I need.

By-the-by, any reason that you made it a generic package? More a
loaded question than you'd expect. What I tend to do, and to encourage
others to do, is to separate what needs to be 'generic' from what
needs not be 'generic' but is required for the generic package to
execute. In my own (very recent experience) I developed a
doubly-linked list. List management is a normal package body. The
generic package provides space, in the generic body, and interfaces to
the non-generic list manager. The effect is to have a no-cost generic
package interfacing with a shared non-generic package. (And so I'm on
a mission - sigh).

Anyway. Thanks. 

art

Re: Singular Value Decomposition (SVD) Ada Algorithm

[John Woodruff]

aschwarz@acm.org (skidmarks) wrote in message news:<35f054ea.0410302259.7510a56e@posting.google.com>...
> > 
> > You can acquire the Drexel U Matrix Math items from  
> > http://dflwww.ece.drexel.edu/research/ada/
> > They are marked:
> > -- Copyright (c) Drexel University, 1996           
            
> > Their package  Generic_Real_Arrays.Operations defines a subprogram
> > "Singular_Value_Decomposition".
> > 
> > This might be what you want!
> 
> Thank you. I haven't looked closely but have looked enough (to say) it
> seems to be what I need.
> 
> By-the-by, any reason that you made it a generic package? 

Well, it wasn't I who did the making.  But I'll offer the
"conventional" explanation:  application writers are wise to select
specific types to represent the numeric quantities, and the generic
formal in such packages as "generic_real_arrays" is instantiated to
reflect those application-specific types.


<...> I developed a
> doubly-linked list. List management is a normal package body. The
> generic package provides space, in the generic body, and interfaces to
> the non-generic list manager. The effect is to have a no-cost generic
> package interfacing with a shared non-generic package. 

I'm not sure I followed that claim;  you might consider posting an
example (folks here are pretty constructive, so you won't get
pilloried :)

However when I read "generic package provides space", I interpret that
to mean maybe you're coercing lots of different "components" of some
list, using 'address' to manage memory (?).  If that's your
suggestion, I don't think I'll agree.

In any event, I don't think there is a "cost" argument in favor of
avoiding generics -- but I'm interested in the discussion.

John

Re: Singular Value Decomposition (SVD) Ada Algorithm

[skidmarks]

> <...> I developed a
> > doubly-linked list. List management is a normal package body. The
> > generic package provides space, in the generic body, and interfaces to
> > the non-generic list manager. The effect is to have a no-cost generic
> > package interfacing with a shared non-generic package. 
> 
> I'm not sure I followed that claim;  you might consider posting an
> example (folks here are pretty constructive, so you won't get
> pilloried :)

Sorry. To be brief:
1. Optimization of data via generics was avoided. All data is 32-bits.
   The rationale is:
   a. If size optimized and packed, more instructions are required
      during operation for (un)packing operations, which increases
      total size, and with more instructions there is decreased
performance.
      (The size is relative and depends on use. Performance is bad.)
   b. If size optimized and unpacked, then depending on the CPU, slack
      bytes are added which increases the size.
   c. By making all sizes the same, the issue becomes movement into
      and out of the fixed size datum field.
2. The List Manager handles all list operations, insertion, deletion,
   data changes, and is invariant to any application.
3. The generics:
   a. Handles transmission of data to/from cell datum fields.
   b. Creates a free list (an array of cells) in the generic body.
   c. At instantiation, populate the free list.
   d. Provide an interface to the List Manager and some application
      niceties not supported by the List Manager.

At the end, the generic functions are all pragma inline and reference
the List Manager. Data specific issues are addressed in the generic
package which converts data from the user type to the List Manager
type via an Unchecked_Conversion, which I assume requires the
generation of no code for data which have the same size.

The application then does (something like): (Ada like not like Ada):

    package List is new Generic (data_type);

begin

    Cell := List.Push(local data);
    Cell := List.Delete(Cell);
    List.etc
end <>;

A List Manager equivalent function is:

     function Push( List, Cell ) return Cell_Adr_Ptr;

and the Generic functions which make this happen is:

     function Push( Data ) return Cell_Adr_Ptr is
     begin
        return List_Manager.Push( List, Set_Data(
Unchecked_Conversion(Data), NUCELL));
     end Push;
     pragma inline ( Push );

where:
    NUCELL   creates a new cell from the available space list
    Set_Data puts a datum into a cell
    List     is known only to the generic (the list is created
             in the generic body.

And sorry, this is way too long winded. The final result is that there
is a division of responsibility which (I believe) provides an adequate
level of encapsulation and information hiding while giving some
application level conveniences. The generic acts as a no-cost
intermediate level (no code or very little code) to the general
purpose list manager functions.

There is always room for comment and architectural changes. A dialog
will always be appreciated.

art

Re: Singular Value Decomposition (SVD) Ada Algorithm

[John Woodruff]

aschwarz@acm.org (skidmarks) wrote in message news:<35f054ea.0411010817.52bbf8fc@posting.google.com>...

> > <...> I developed a doubly-linked list. 
<...>

I guess since I might have induced you to show us your thinking, it's
proper I offer my remarks.


> 1. Optimization of data via generics was avoided. All data is 32-bits.
>    The rationale is:
>    a. If size optimized and packed, more instructions are required
>       during operation for (un)packing operations, which increases
>       total size, and with more instructions there is decreased
> performance.
>       (The size is relative and depends on use. Performance is bad.)
>    b. If size optimized and unpacked, then depending on the CPU, slack
>       bytes are added which increases the size.
>    c. By making all sizes the same, the issue becomes movement into
>       and out of the fixed size datum field.

Let me say that I have no idea what requirements you're working to. 
If you're working in a context with a few tens of kilobytes of memory,
or with a 100 Khz processor, or the like, I can sympathize with your
effort to crowd every last particle of performance.

However in my own life, I have stuck with an aphorism on the topic of
optimization that I picked up 30 or so years ago:
There are two guidelines for micro-optimization:
   -- Don't do it
   -- Don't do it yet.

<...>

> The final result is that there
> is a division of responsibility which (I believe) provides an adequate
> level of encapsulation and information hiding while giving some
> application level conveniences. 

My thought is that you have not encapsulated quite as much as you
might have done.  At the outset, you said "All data is 32-bits".  But
I can think of *a lot* of data that don't comply.  And your list
handler doesn't cover those.  So someday you might need to repeat the
effort you expended in order to build a new one.  Or, even worse, you
or your successor will forget the restrictions and reuse your list
manager with a non-32bit-compliant component, and the result might not
be pretty.

My committment to software engineering was (before I retired) to try
to leave lasting artifacts that will function for *decades* in
evolving service.  The tactics that Ada promotes helped me do that, I
think.  Other folks have other goals, I guess

> There is always room for comment and architectural changes. A dialog
> will always be appreciated.
>

I enjoy the occasional dialog!
John

Re: Singular Value Decomposition (SVD) Ada Algorithm

[Jeffrey Carter]

John Woodruff wrote:

> However in my own life, I have stuck with an aphorism on the topic of
> optimization that I picked up 30 or so years ago:
> There are two guidelines for micro-optimization:
>    -- Don't do it
>    -- Don't do it yet.

As I learned it, more like 25 years ago:

1. Don't do it

2. If you must do it, don't do it yet.

3. If you still must do it, see 1.

-- 
Jeff Carter
"It's symbolic of his struggle against reality."
Monty Python's Life of Brian
78

Re: Singular Value Decomposition (SVD) Ada Algorithm

[skidmarks]

jpwoodruff@irisinternet.net (John Woodruff) wrote in message news:<34defe4d.0411052123.49702f47@posting.google.com>...
> aschwarz@acm.org (skidmarks) wrote in message news:<35f054ea.0411010817.52bbf8fc@posting.google.com>...
> 
> > > <...> I developed a doubly-linked list. 
> <...>
> 
>
> My committment to software engineering was (before I retired) to try
> to leave lasting artifacts that will function for *decades* in
> evolving service.  The tactics that Ada promotes helped me do that, I
> think.  Other folks have other goals, I guess

> I enjoy the occasional dialog!

And so I do.

Well, you've (and others) given several point of thought. Quickly, let
me address some:

I learned: 
  1. There are no absolutes in software.
  2. Look at the issues before you solve the problem.

In this light there are some notes.

Issue: The CPU is of limited capability in an embedded, critical
real-time environment. It is very important to conserve space and save
speed.

The tendered solution seems to solve the issue without compromising
system integrity. Programmer optimization is often not required, and
more often should not be done (because the compiler does it better and
good code is preserved). It is a mistake to say 'never'. It is better
to address whether this is an appropriate time to consider
optimization by the programmer rather than it is always a mistake for
the programmer to 'hand' optimize. I did consider the optimization
issues, and did mention them. My opinion is that this a case when the
compiler will do more damage than good.

Let's consider an example. Hopefully there are counter-examples
available which solve the same problems which you are aware of and I
am not.

Suppose that our data size is a Boolean, and suppose further that we
conserve space by using 'pragma packed'. A baseline requirement is
that pointers be used, and not just indices, and I am left with
something like:

(Please correct and glaring Ada errors, but understand that this is
just for explication of a viewpoint not for delivery of a product).

   type Cell_Ptr_Type;

   type Cell_Type is 
     record
       Previous:   Cell_Ptr_Type;
       Next    :   Cell_Ptr_Type;
       Data    :   Boolean;
     end record;

   type Cell_Ptr_Type is access all Cell_Type;

   type List_Type(Size: Natural) is
     record
       Active: Cell_Type;    -- Active List Pointer
       Free  : Cell_Type;    -- Available Space List
       Space : array(1..Size) of aliased Cell_Type;
     end record;

   List : List_Type; pragma packed( List );

(Hopefully the Ada isn't too wrong).

Now one thing that my approach allows is the complete recovery of all
list management functions (inserting, deleting, etc.). This translates
into not using a generic for list management and not needing to
replicate the list management code for each instance of use with a new
type.

Another advantage(?) is that non-homogenous lists are supported,
provided that the datum size fits into the specified size.

Another advantage(?) is that processing overhead is minimized because
(in my case) advantage is taken of computer data access
characteristics, in this case alignment of cells are on _proper_
boundaries.

A disadvantage is that more space is consumed. Given my previous
example and looking at the above, 31-bits are wasted for each cell.

My point is that the advantages exceed the disadvantages. In
particular, the 31-bits lost per cell may be gained when the cost of
data plus instruction size (to manipulate the lists) plus instruction
size (to access data) plus instruction size (for generic copies of the
list management functions) are all included.

In general terms, the largest list management routine is (about) 10
SLOC and the remainder vary between 1 - 4 SLOC. Unless the maintainers
come from a non-software degree, I wouldn't expect much thought in
this case, and I have mentioned that issues should be considered
before solutions.

And is there a suitable counter-example? 

thanks

PS: I only mention this because age seems to be a prominent
characteristic in some of the responses. When I went to college it was
relayed to me that statistically unless you made your mark in Physics,
Mathematics, or Philosophy before age 25 you never would. Mozart
composed a number of good compositions prior to his 20th birthday. And
I would rather be young than wise.

Re: Singular Value Decomposition (SVD) Ada Algorithm

[Gautier Write-only]

skidmarks:

> Anyone have an SVD in Ada? I have the C/C++ versions from Numerical
> Recipes in C++ (I have the CD-ROM) and would rather not rewrite it
> into Ada unless I have to.

For SVD you have an answer; for other algorithms from the N.R. you
can translate the Pascal version (freely available) via P2Ada. See
  http://homepage.sunrise.ch/mysunrise/gdm/gsoft.htm#p2ada

HTH
________________________________________________________
Gautier  --  http://www.mysunrise.ch/users/gdm/gsoft.htm

NB: For a direct answer, e-mail address on the Web site!