User:Bumi: Difference between revisions

From Octave
Jump to navigation Jump to search
 
(8 intermediate revisions by the same user not shown)
Line 33: Line 33:
* Please state the commits and patches you already contributed to Octave.
* Please state the commits and patches you already contributed to Octave.
** [https://savannah.gnu.org/bugs/?36437 bug #36437]
** [https://savannah.gnu.org/bugs/?36437 bug #36437]
** '''Currently I am working on [http://wiki.octave.org/User:Bumi#Preliminary_balancing Preliminary balancing]'''
*** '''[https://savannah.gnu.org/patch/?8960 patch #8960]'''
*** [http://pastebin.com/CBBUYYDW EIG.cc]
*** [http://pastebin.com/9met8n18 EIG.h]
*** [http://pastebin.com/9PZLTd48 fEIG.cc]
*** [http://pastebin.com/Z6RifG2i fEIG.h]
*** [http://pastebin.com/RJ6Fi04f eig.cc]
*** And I also created a diff file
****  [http://pastebin.com/C7PhbzVS diff]


== F: Feeling fine ==
== F: Feeling fine ==
Line 79: Line 88:
* Please provide a rough estimated timeline for your work on the task.
* Please provide a rough estimated timeline for your work on the task.


=== Project goals===
I chose the '''[http://wiki.octave.org/Summer_of_Code_Project_Ideas#Generalised_eigenvalue_problem Generalised eigenvalue problem]'''.
I chose the '''[http://wiki.octave.org/Summer_of_Code_Project_Ideas#Generalised_eigenvalue_problem Generalised eigenvalue problem]'''.


Line 110: Line 120:
=== Timeline ===
=== Timeline ===
* '''Community Bonding period''' (Until May 22)
* '''Community Bonding period''' (Until May 22)
** Get acquainted with the code and LAPACK
** Get acquainted with the code and LAPACK, <u>finish most of  preliminary balancing</u>
* '''Week 1-2''' (May 23 - Jun 5)
* '''Week 1-2''' (May 23 - Jun 5)
** Finals, non-coding time
** Finals, non-coding time
Line 118: Line 128:
* '''Midterm evaluations''' (Jun 20 - Jun 27)
* '''Midterm evaluations''' (Jun 20 - Jun 27)
* '''Week 6''' (Jun 27 - Jul 3)
* '''Week 6''' (Jun 27 - Jul 3)
** Implementing preliminary balancing, testing
** <s>Implementing preliminary balancing, testing</s>
* '''Week 7-10''' (Jul 4 - Jul 31)
* '''Week 7-10''' (Jul 4 - Jul 31)
** algorithm choosing for eigenvalue calculation (chol or qz)
** algorithm choosing for eigenvalue calculation (chol or qz)
Line 156: Line 166:


* The Matlab documentation does not mention whether there is balancing in the generalised case, but if needed the *ggevx could be used same.
* The Matlab documentation does not mention whether there is balancing in the generalised case, but if needed the *ggevx could be used same.
** '''EDIT:''' In Matlab there is no balance option in the generalised case:
* IN:
{{Code|Matlab's eig|<syntaxhighlight lang="matlab">
A = [1, 2 ; 3, 4]
B = [5, 6 ; 7, 8]
e = eig(A, B, 'nobalance')
</syntaxhighlight>}}
* OUT:
Error using eig
For generalized eigenproblem EIG(A,B), flag must be 'vector', 'matrix', 'qz', or 'chol'.


==== Computing left eigenvectors as a third output ====
==== Computing left eigenvectors as a third output ====
* *geevx and *ggeevx could also be used as these can compute not just right but left eigenvalues also.
* *geevx and *ggevx could also be used as these can compute not just right but left eigenvectors also.


==== Choosing among generalized eigenvalue algorithms ====
==== Choosing among generalized eigenvalue algorithms ====
Line 191: Line 212:
|-
|-
| [http://www.netlib.org/lapack/explore-html/d9/d8e/group__double_g_eeigen.html#ga4e35e1d4e9b63ba9eef4ba8aff3debae dgeevx]
| [http://www.netlib.org/lapack/explore-html/d9/d8e/group__double_g_eeigen.html#ga4e35e1d4e9b63ba9eef4ba8aff3debae dgeevx]
| rowspan="2" | Computing right and left eigenvectors, optionally eigenvalues, with balance option
| rowspan="4" | Computing right and left eigenvectors, optionally eigenvalues, with balance option
|-
|-
| [http://www.netlib.org/lapack/explore-html/db/d55/group__complex16_g_eeigen.html#gae55acf82651540f7d8f36715eec0900d zgeevx]
| [http://www.netlib.org/lapack/explore-html/db/d55/group__complex16_g_eeigen.html#gae55acf82651540f7d8f36715eec0900d zgeevx]
|-
| [http://www.netlib.org/lapack/explore-html/d3/dfb/group__real_g_eeigen.html#gadf06d28b4793cbab21e898fcb713d5a5 sgeevx]
|-
| [http://www.netlib.org/lapack/explore-html/d4/d8a/group__complex_g_eeigen.html#ga397ffbf0007d6b72f4639379df27ae53 cgeevx]
|-
|-
| [http://www.netlib.org/lapack/explore-html/d9/d8e/group__double_g_eeigen.html#ga58099bb0f4ebe6a1f6f6078e05a6fb78 dggevx]
| [http://www.netlib.org/lapack/explore-html/d9/d8e/group__double_g_eeigen.html#ga58099bb0f4ebe6a1f6f6078e05a6fb78 dggevx]
| rowspan="2" | Computing generialized eigenvalues, optionally right and left generalised eigenvectors, with balance option
| rowspan="4" | Computing generialized eigenvalues, optionally right and left generalised eigenvectors, with balance option
|-
|-
| [http://www.netlib.org/lapack/explore-html/db/d55/group__complex16_g_eeigen.html#gaad769423756706f1186027c9dd7615e4 zggevx]
| [http://www.netlib.org/lapack/explore-html/db/d55/group__complex16_g_eeigen.html#gaad769423756706f1186027c9dd7615e4 zggevx]
|-
| [http://www.netlib.org/lapack/explore-html/d3/dfb/group__real_g_eeigen.html#ga6176eadcb5a027beb0b000fbf74f9e35 sggev]
|-
| [http://www.netlib.org/lapack/explore-html/d4/d8a/group__complex_g_eeigen.html#gad681a6edd407ef1e9ac9b6ee92ddbee3 cggevx]
|-
|-
| [http://www.netlib.org/lapack/explore-html/d2/d8a/group__double_s_yeigen.html#ga442c43fca5493590f8f26cf42fed4044 dsyev]
| [http://www.netlib.org/lapack/explore-html/d2/d8a/group__double_s_yeigen.html#ga442c43fca5493590f8f26cf42fed4044 dsyev]
| rowspan="2" | Computing all eigenvalues, optionally eigenvectors for Hermitan/Symmetric matrix
| rowspan="4" | Computing all eigenvalues, optionally eigenvectors for Symmetric/Hermitan matrix
|-
| [http://www.netlib.org/lapack/explore-html/d3/d88/group__real_s_yeigen.html#ga63d8d12aef8f2711d711d9e6bd833e46 ssyev]
|-
|-
| [http://www.netlib.org/lapack/explore-html/d6/dee/zheev_8f.html#af23fb5b3ae38072ef4890ba43d5cfea2 zheev]
| [http://www.netlib.org/lapack/explore-html/d6/dee/zheev_8f.html#af23fb5b3ae38072ef4890ba43d5cfea2 zheev]
|-
| [http://www.netlib.org/lapack/explore-html/df/db2/cheev_8f.html#a003ee37091d65ee62fd72da1035f06e2 cheev]
|-
|-
| [http://www.netlib.org/lapack/explore-html/d2/d8a/group__double_s_yeigen.html#ga007d33bcdcc697e17c6d15432f159b73 dsygv]
| [http://www.netlib.org/lapack/explore-html/d2/d8a/group__double_s_yeigen.html#ga007d33bcdcc697e17c6d15432f159b73 dsygv]
| rowspan="2" | Generalised
| rowspan="4" | Generalised
|-
| [http://www.netlib.org/lapack/explore-html/d3/d88/group__real_s_yeigen.html#ga0523956327948aae43173b964188e5a2 ssygv]
|-
|-
| [http://www.netlib.org/lapack/explore-html/dd/de2/zhegv_8f.html#af7b790b3b89de432a423c9006c1cc1ac zhegv]
| [http://www.netlib.org/lapack/explore-html/dd/de2/zhegv_8f.html#af7b790b3b89de432a423c9006c1cc1ac zhegv]
|-
| [http://www.netlib.org/lapack/explore-html/d0/db9/chegv_8f.html#ab2f86fb41df5ae239798c9c3081a2d49 chegv]
|-
|-
| [http://www.netlib.org/lapack/explore-html/d1/d7a/group__double_p_ocomputational.html#ga2f55f604a6003d03b5cd4a0adcfb74d6 dpotrf]
| [http://www.netlib.org/lapack/explore-html/d1/d7a/group__double_p_ocomputational.html#ga2f55f604a6003d03b5cd4a0adcfb74d6 dpotrf]
| rowspan="2" | For Cholesky factorization
| rowspan="4" | For Cholesky factorization
|-
|-
| [http://www.netlib.org/lapack/explore-html/da/d7a/_v_a_r_i_a_n_t_s_2cholesky_2_r_l_2zpotrf_8f.html#a93e22b682170873efb50df5a79c5e4eb zpotrf]
| [http://www.netlib.org/lapack/explore-html/da/d7a/_v_a_r_i_a_n_t_s_2cholesky_2_r_l_2zpotrf_8f.html#a93e22b682170873efb50df5a79c5e4eb zpotrf]
|-
| [http://www.netlib.org/lapack/explore-html/d8/db2/group__real_p_ocomputational.html#gaaf31db7ab15b4f4ba527a3d31a15a58e spotrf]
|-
| [http://www.netlib.org/lapack/explore-html/d6/df6/group__complex_p_ocomputational.html#ga4e85f48dbd837ccbbf76aa077f33de19 cpotrf]
|-
|}
|}

Latest revision as of 01:01, 27 June 2016

GSoC 2016 application[edit]

A: An introduction[edit]

  • Please describe yourself in three sentences, one of them regarding your current studies.
    • My name is Barbara Lócsi, I am a Hungarian first year undergraduate software engineering student at the Budapest University of Technology and Economics. I like math, programing, reading novels and solving Rubik's Cubes. I am determined and dedicated, and if I set a goal I won't stop until it is reached.
  • Which languages do you speak?
    • Hungarian (native), English (fluent)
  • What's your overall background?
    • Computer science.
  • Why do you want to participate in the Google Summer of Code? What do you hope to gain by doing so?
    • Before looking into GSoC and the organizations I didn't really know much about open source and free softwares. Obviously, I have heard about it, but just thought that I can look on its source code and that's all. I didn't realized before, that I can actually contribute and that it is welcomed by the community. I believe Google Summer of Code is a really good opportunity to get into open-source or free development. And also I am here to learn, gain experience and extend knowledge.
  • Please also describe your previous experience with the GSoC, if any.
    • I have no prior experience with GSoC, I just know about it for about a month.
  • Why are you choosing Octave?
    • In the last semester I had a course on which I have learned about linear algebra and I really liked it. So when I was wandering around and saw the "Generalised eigenvalue problem" project idea, I was really interested in it and excited to know more about it.

C: Contact[edit]

  • Please state the nick you use on IRC and any other communication channel related to Octave.
    • Bumi or bumi
  • Which time zone do you live in? Will that change over GSoC duration?
    • UTC+2 during summer, it is unlikely to change.
  • Please state the timeframe (in UTC+0) when you feel most comfortable working during GSoC. Where are your time buffers?
    • Anything between 8:00 to 20:00 is good for me and could try to stay for bit later when needed.

E: Coding experience[edit]

  • Please describe your experience with C++, Octave or Matlab m-scripts, OpenGL and Qt.
    • I am learning C++ in this semester. I have no prior experience with the rest, but started using and learning about Octave and Matlab by myself.
  • Please describe your experience with other programming languages.
    • I had a C course in the previous semester, and also learned a bit Assembly. Before these I used C# for my own pet projects.
  • Please describe your experience with being in a development team.
    • I have no experience.
  • Please describe the biggest project you have written code for and what you learned by doing so. Also describe your role in that project over time.
    • I created a snake game in C (using SDL) as homework for the previous semesters programing course. It was an independent task so I did all of the work. For example I learned using SDL, dynamic memory allocation, handling independent .c and .h files.
  • Please state the commits and patches you already contributed to Octave.

F: Feeling fine[edit]

  • Please describe (in short) your experience with the following tools:
    • IRC and mailing lists
      • I am using IRC and have used mail list before. I am also subscribed to octave-maintainers.
    • Mercurial or other source code management systems
      • Just started using mercurial, not so much experience with others.
    • Mediawiki or other wiki software
      • I haven't used it before.
    • make, gcc, gdb or other development tools
      • Just started using make gcc and gdb, got help from IRC and google is my friend.
  • What will make you actively stay in our community after this GSoC is over?
    • I will have a course in the next semester that uses Matlab so probably I will be around if I have time.

O: Only out of interest[edit]

  • Did you ever hear about Octave before?
    • No, I did not.
    • If not, where would you expect or advise us to do advertising?
  • What was the first question concerning Octave you could not find an answer to rather quickly?
    • How to search in mail list archives? nabble

P: Prerequisites[edit]

  • Please state the operating system you work with.
    • I have Windows 10 and Debian 8 on virtual machine, it is my own laptop I have complete access.
  • Please estimate an average time per day you will be able to access
    • an internet connection
      • 24h
    • a computer
      • 24h
    • a computer with your progressing work on
      • 24h
  • Please describe the degree to which you can install new software on computers you have access to.
    • Complete access.

S: Self-assessment[edit]

  • Please describe how useful criticism looks from your point of view as committing student.
    • I like to receive advices, guides, help, and useful criticism as it helps my progression and I can learn from it.
  • How autonomous are you when developing:
    • Do you like to discuss changes intensively and not start coding until you know what you want to do?
      • I like to be full aware of the task and the aims before starting coding.

Y: Your task[edit]

  • Did you select a task from our list of proposals and ideas?
    • If yes, what task did you choose? Please describe what part of it you especially want to focus on if you can already provide this information.
  • Please provide a rough estimated timeline for your work on the task.

Project goals[edit]

I chose the Generalised eigenvalue problem.

Certain calling forms of the eig function are currently missing, including:

  • preliminary balancing
  • computing left eigenvectors as a third output
  • choosing among generalized eigenvalue algorithms
  • choosing among return value formats of the eigenvalues (vector or matrix) see more here.

The project's aim is to implement these functionalities.

Matlab Octave
  • e = eig(A)
  • [V,D] = eig(A)
  • [V,D,W] = eig(A)
  • e = eig(A,B)
  • [V,D] = eig(A,B)
  • [V,D,W] = eig(A,B)
  • [___] = eig(A,balanceOption)
  • [___] = eig(A,B,algorithm)
  • [___] = eig(___,eigvalOption)
  • lambda = eig (A)
  • lambda = eig (A, B)
  • [V, lambda] = eig (A)
  • [V, lambda] = eig (A, B)

Timeline[edit]

  • Community Bonding period (Until May 22)
    • Get acquainted with the code and LAPACK, finish most of preliminary balancing
  • Week 1-2 (May 23 - Jun 5)
    • Finals, non-coding time
  • Week 3-4 (Jun 6 - Jun 19)
    • Add left eigenvector calculation
    • Creating tests
  • Midterm evaluations (Jun 20 - Jun 27)
  • Week 6 (Jun 27 - Jul 3)
    • Implementing preliminary balancing, testing
  • Week 7-10 (Jul 4 - Jul 31)
    • algorithm choosing for eigenvalue calculation (chol or qz)
    • creating tests
  • Week 11 (Aug 1 - Aug 7)
    • documenting
  • Week 12-13 (Aug 8 - Aug 28)
    • deciding return value format of the eigenvalues (vector or matrix)
    • testing, documenting

Implementation[edit]

Preliminary balancing[edit]

  • In Octave currently the preliminary balancing is not done in eig, while in Matlab the balancing is default and it can be turned out by 'nobalance'. (In the standard eigenvalue problem)
  • The ability to turn off the balancing is important as:
Balancing can destroy the properties of certain matrices; use it with some care. If a matrix contains small elements that are due to roundoff error, balancing might scale them up to make them as significant as the other elements of  the original matrix. [1]
  • Syntax of preliminary balancing in Matlab:
[___] = eig(A,balanceOption)
  • Where the default for balanceOption is 'balance' and it can be changed to 'nobalance':
balanceOption — Balance option 
 'balance' (default) | 'nobalance'
  • In Octave currently the *geev LAPACK function is used. Using the extended *geevx function instead would allow to enable balancing. It not just allows 'balance' and 'nobalance' option it provides 4 modes:
BALANC is CHARACTER*1
Specifies the balance option to be performed.
= 'N':  do not diagonally scale or permute;
= 'P':  permute only;
= 'S':  scale only;
= 'B':  both permute and scale.
Computed reciprocal condition numbers will be for the
matrices after permuting and/or balancing. Permuting does
not change condition numbers (in exact arithmetic), but
balancing does.
  • The Matlab documentation does not mention whether there is balancing in the generalised case, but if needed the *ggevx could be used same.
    • EDIT: In Matlab there is no balance option in the generalised case:
  • IN:
Code: Matlab's eig
A = [1, 2 ; 3, 4]
B = [5, 6 ; 7, 8]
e = eig(A, B, 'nobalance')
  • OUT:
Error using eig
For generalized eigenproblem EIG(A,B), flag must be 'vector', 'matrix', 'qz', or 'chol'.

Computing left eigenvectors as a third output[edit]

  • *geevx and *ggevx could also be used as these can compute not just right but left eigenvectors also.

Choosing among generalized eigenvalue algorithms[edit]

  • Octave:
The algorithm used depends on whether there are one or two input matrices, if they are real or complex, and if they are symmetric (Hermitian if complex) or non-symmetric.[2]
  • Currently in Octave the algorithm used is the same as in Matlab. It uses the Cholesky factorization if the matrices are symmetric otherwise it uses the QZ algorithm. But in Matlab the user can decide the algorithm directly:
[___] = eig(A,B,algorithm)
  • Where the algorithm can be 'chol' or 'qz'
algorithm — Generalized eigenvalue algorithm 
'chol' | 'qz'
  • But if A or B are not symmetric than it still uses the QZ algorithm

Choosing among return value formats of the eigenvalues[edit]

  • The default return value format is the same in Matlab as in Octave:
If you specify one output, such as e = eig(A), then the eigenvalues are returned as a column vector by default.
If you specify two or three outputs, such as [V,D] = eig(A), then the eigenvalues are returned as a diagonal matrix, D, by default. [3]
  • But in Matlab the default can be changed.
[___] = eig(___,eigvalOption)
  • Where eigvalOption can be 'vector' or 'matrix'
eigvalOption — Eigenvalue option
'vector' | 'matrix'

LAPACK routines[edit]

List of some useful LAPACK routines
dgeevx Computing right and left eigenvectors, optionally eigenvalues, with balance option
zgeevx
sgeevx
cgeevx
dggevx Computing generialized eigenvalues, optionally right and left generalised eigenvectors, with balance option
zggevx
sggev
cggevx
dsyev Computing all eigenvalues, optionally eigenvectors for Symmetric/Hermitan matrix
ssyev
zheev
cheev
dsygv Generalised
ssygv
zhegv
chegv
dpotrf For Cholesky factorization
zpotrf
spotrf
cpotrf