Bumi

GSoC 2016 application

A: An introduction

• 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

• 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

• 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.
  • bug #36437
  • Currently I am working on Preliminary balancing
    • patch #8960
    • EIG.cc
    • EIG.h
    • fEIG.cc
    • fEIG.h
    • eig.cc
    • And I also created a diff file
      • diff

F: Feeling fine

• 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

• 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

• 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

• 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

• 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

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

• 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

Preliminary balancing

• 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

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

Choosing among generalized eigenvalue algorithms

• 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

• 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

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