#!/usr/bin/env python3
# -*- coding: utf-8 -*-

#' # Aufgabe 49: Kompakte QR-Zerlegung, Teil 1

import numpy as np

def QR_kompakt(A):
    ''' Berechnet die QR-Zerlegung der Matrix A aus R^{mxn}
    Input: Matrix A
    Output: alphas, neues Array mit vs und teilweise R
    '''
    # Zur besseren Unterscheidung wird hier R in V umbenannt. An 
    # den Rechnungen ändert sich nichts, es werden lediglich unnötige 
    # Schritte (Berechnung von Q) weggelassen und zwei Zeilen fürs Speichern 
    # an entsprechenden Stellen zugefügt.
    V = A.astype('float')
    m, n = A.shape
    alphas = np.zeros(n)
    for k in range(n):
        u = V[k:, [k]]
        alpha = -np.sign(V[k, k])*np.linalg.norm(u)
        if alpha == 0:
            alpha = -np.linalg.norm(u)
        alphas[k] = alpha
        u -= alpha*np.eye(m-k, 1)
        for j in range(k+1, n):
            V[k:, [j]] -= (V[k:, [j]].T @ u)*u / (alpha*(alpha-V[k, k]))
        V[k:, [k]] = u / np.linalg.norm(u)
        # oder auch ohne linalg.norm:
        # V[k:, [k]] = u / np.sqrt(2*alpha*(alpha - V[k, k]))
    return alphas, V